Nils and Josh are playing a game!
The game is played on an
At the end, the grid will be cut into either two, three, or four subgrids. Josh wins the game if the number of coins in each subgrid is an even number, and Nils wins otherwise.
Unfortunately, Josh needs to make the first move, so the odds aren't in his favor. So, before the game begins, he will secretly perform a special move! Specifically, he will perform the following operations once, in order.
- Choose a subgrid with the top left corner
and bottom right corner such that and . - Choose a cell
inside the subgrid, formally, one where and . - Stack
more coins on each cell in the subgrid. More specifically, simultaneously set the integer in cell to for all .
Can you help Josh find a way to ensure that he will always win after performing the special move exactly once, or tell him that is impossible to do so?
Constraints
Subtask 1 [5%]
Subtask 2 [15%]
Subtask 3 [30%]
Subtask 4 [50%]
No additional constraints.
Input Specification
The first line contains two integers
The next
Output Specification
If it is impossible for Josh to guarantee a win after performing the special move, output
Otherwise, on the first line, output two space-separated integers
Then, on the second line, output two space-separated integers
Then, on the third line, output two space-separated integers
Then, on the fourth line, output R
or C
followed by a space-separated integer
If there are multiple possible outputs, you may output any of them.
Sample Input 1
5 6
3 5 8 3 0 9
2 4 3 8 5 7
1 2 6 0 9 6
8 3 4 0 4 9
8 7 0 8 6 9
Sample Output 1
2 2
2 4
2 3
R 3
Explanation for Sample Output 1
Josh can choose the subgrid from
Afterwards, by making a horizontal cut between row
Sample Input 2
4 4
6 6 5 1
0 3 4 3
6 9 6 5
6 6 1 7
Sample Output 2
2 2
3 3
3 2
C 2
Explanation for Sample Output 2
Josh can choose the subgrid from
Afterwards, by making a vertical cut between column
Sample Input 3
2 2
1 4
2 3
Sample Output 3
-1
Explanation for Sample Output 3
It can be shown that Josh can never guarantee a win after performing the special move. An example is provided below. In the example, Josh chooses the subgrid from
Then, no matter what cut Josh makes, Nils will always be able to create at least one subgrid with an odd number of coins. It can also be shown for any other possible special move that Josh can perform that Nils will still be able to win.
Comments