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!


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.



  • 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
1 1 4 3
2 3 3 5
Sample Input 2 Sample Output 2
4 5
1 5 4 5
1 5 3 5
Sample Input 3 Sample Output 3
3 5

Please log in to submit a solution to this problem

Log in