OpenKattis
CS3233 Midterm Team Contest

Start

2019-04-01 09:00 UTC

CS3233 Midterm Team Contest

End

2019-04-01 13:30 UTC
The end is near!
Contest is over.
Not yet started.
Contest is starting in -226 days 0:17:15

Time elapsed

4:30:00

Time remaining

0:00:00

Problem D
Daring Don't

Rainbow Dash and Daring Do have rushed into the Fortress of Talacon, and they need to solve an ancient puzzle to open the doorway to the treasure of the fortress, a large golden ring.

The puzzle consists of a large grid on the floor, having $R$ rows and $C$ columns. Each cell in the grid contains either an x or an o.

Rainbow and Daring need to make exactly two moves, such that after those two moves, the number of x’s and o’s in the grid are equal. (It is possible that the number of x’s and o’s in the grid are already equal—however, they still need to make two moves.)

In each move, Rainbow and Daring must step on two different cells. If Rainbow steps on the cell at row $r_1$ and column $c_1$, and Daring steps on the cell at row $r_2$ and column $c_2$, then, for every cell, if we denote its row by $r$ and its column by $c$, the symbol on the cell flips from x to o (and vice-versa) if and only if $\min (r_1, r_2) \leq r \leq \max (r_1, r_2)$ and $\min (c_1, c_2) \leq c \leq \max (c_1, c_2)$ both hold. Note that they can step on the same pair of cells for their first and second move; there is no restriction in this regard.

\includegraphics[width=0.7\textwidth ]{daring.png}
Figure 1: Illustration of Sample Input 1.

If Rainbow and Daring fail to solve this puzzle, they will not be able to retrieve the treasure of the fortress and the evil Dr. Caballeron will reign unchecked. Please, help them!

Input

The first line of input contains two integers, $R$ and $C$ ($1 \leq R, C$; $2 \leq R\cdot C \leq 4\cdot 10^6$), the number of rows and the number of columns of the grid, respectively.

The next $R$ lines each contain a string of $C$ characters. In particular, the $j^\text {th}$ character on the $i^\text {th}$ of these lines contains either x or o, denoting the character at the $i^\text {th}$ row and $j^\text {th}$ column of the grid.

Output

Output:

  • two lines, where the $i^\text {th}$ of these lines contains four integers, $r_1$, $c_1$, $r_2$ and $c_2$ ($1 \leq r_1, r_2 \leq R$; $1 \leq c_1, c_2 \leq C$; either $r_1 \neq r_2$ or $c_1 \neq c_2$), describing the cells Rainbow and Daring should step on, for the $i^\text {th}$ move, respectively, if a solution exists, or

  • a single line containing the string IMPOSSIBLE, otherwise.

If there are multiple correct answers, you can output any of them.

Sample Input 1 Sample Output 1
4 5
oooxx
xxoxx
xxoxx
oooxx
1 1 4 3
2 3 3 5
Sample Input 2 Sample Output 2
4 5
xxxxx
xxxxx
ooooo
oooox
1 5 4 5
1 5 3 5
Sample Input 3 Sample Output 3
3 5
ooooo
ooooo
ooooo
IMPOSSIBLE