Penelope is playing a game on an grid! Her grid currently contains s, while the rest of her grid cells contain s.
Penelope isn't sure she likes her grid though. Specifically, she is worried that her grid isn't beautiful. A grid is beautiful if every row sum and column sum are even.
Penelope is in a hurry to make her grid beautiful so she asks you: how can she make her grid beautiful? On each move, you can flip the value of a grid cell: from to or to . Since she is in a hurry, she asks you to make her grid beautiful as fast as possible.
All cells given are distinct.
Subtask 1 [30%]
Subtask 2 [70%]
No additional constraints.
The first line contains integers, , the number of rows; , the number of columns; and .
The next lines each contain two integers and , indicating that the cell in the row, column contains a .
On the first line output , the minimum number of moves required to make the grid beautiful. must satisfy . It can be proven that the minimum lies within this range.
On the next lines, output two space-separated integers and , indicating that you will flip the cell in the row, column.
You may output any valid sequence.
Note: your output must follow the standard convention of not having any extra whitespace, and it must end with a new line.
If you output an incorrect value , but a valid sequence of moves, you will receive for that test case.
If you output a correct value , but an invalid sequence of moves, you will receive for that test case.
If you output a correct value of and any valid sequence of moves, you will receive for that test case.
Your score for a subtask will be the minimum score across all test cases of that subtask.
2 3 3
Note that after our operation, our grid is:
1 0 1
1 0 1
which satisfies the constraints.