## Yet Another Contest 4 P4 - Even The Odds

View as PDF

Points: 20 (partial)
Time limit: 2.0s
Memory limit: 512M

Author:
Problem types

Nils and Josh are playing a game!

The game is played on an grid, and each cell in the grid has been filled with a non-negative number of coins. Denote the cell in the -th row from the top and -th column from the left by . To play the game, each player will select either a row where or a column where . If a row was selected, a cut across the grid is made between row and row . If a column was selected instead, a cut across the grid is made between column and column . Josh and Nils will each make exactly one move, with Josh going first. Nils is allowed to make the same cut as Josh.

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?

#### Input Specification

The first line contains two integers and .

The next lines each contain integers , representing the cells of the grid.

#### Output Specification

If it is impossible for Josh to guarantee a win after performing the special move, output on a line by itself.

Otherwise, on the first line, output two space-separated integers and , representing the top left boundary of the subgrid chosen for the special move.

Then, on the second line, output two space-separated integers and , representing the bottom right boundary of the subgrid chosen for the special move.

Then, on the third line, output two space-separated integers and , representing the selected cell within the subgrid for the special move.

Then, on the fourth line, output R or C followed by a space-separated integer , denoting that Josh is making either a horizontal cut between row and row or a vertical cut between column and column .

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 to , then stack more coins onto each cell in the subgrid.

Afterwards, by making a horizontal cut between row and row , Josh will be able to guarantee that he wins regardless of what cut Nils makes. Below are a few examples of cuts that Nils can make (represented with a red line). Notice that the number of coins in each subgrid is always even.

#### 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 to , then stack more coins onto each cell in the subgrid.

Afterwards, by making a vertical cut between column and row , Josh will be able to guarantee that he wins regardless of what cut Nils makes. Again, below are a few examples of cuts that Nils can make. Notice that the number of coins in each subgrid is always even.

#### 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 to , then stacks more coins onto each cell in the subgrid.

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.