Some UTS students want to sneak in to the mythical Room 666, where it is rumoured that the report cards are kept. However, the teachers have devised an complex lock system to prevent students from opening the door. The lock consists of many switches arranged in a diamond shape like this:
Some switches are set to open (~0~), while others are set to closed (~1~). In order to unlock the door, all switches must be set to open. The students can flip any switch they want (changing its value from ~0~ to ~1~, or from ~1~ to ~0~), and they can do this at most ~10^6~ times. However, when a switch is flipped, all switches in the same row or column get flipped too. The students are puzzled by this elaborate contraption, so they ask you to unlock it! For the sake of these students' grades, help them find a sequence of flips that will unlock the door.
The first line contains the even integer ~N~ ~(1 \le N \le 1000)~, the height and width of the diamond-shaped lock. The next ~N~ lines contain ~N~ characters each: either a
0 (an open switch),
1 (closed switch), or
. (no switch).
Output any sequence of flips that will unlock the door as follows: on the first line, print ~M~ ~(0 \le M \le 10^6)~, the number of flips in your sequence. On the next ~M~ lines, print two integers ~r~, ~c~ ~(1 \le r, c \le n)~, indicating that the switch in row ~r~, column ~c~ should be flipped (along with the other switches in row ~r~ or column ~c~). The rows and columns are ~1~-indexed, with the top-left position being ~(1, 1)~ and the bottom-right position being ~(n, n)~. It is guaranteed that such a sequence exists - otherwise, even the teachers wouldn't be able to enter the room!
Subtask 1 [10%]
~1 \le N \le 4~
Subtask 2 [40%]
~1 \le N \le 80~
Subtask 3 [50%]
~1 \le N \le 1000~
Sample Input 1
8 ...10... ..0110.. .011010. 11101011 00110100 .100111. ..1101.. ...10...
Sample Output 1
3 2 4 6 6 4 3
Explanation for Sample Output 1
Here is one possible sequence of flips:
Note that there are multiple solutions, and any solution that requires ~10^6~ flips or less will be accepted.
Sample Input 2
2 10 01
Sample Output 2
2 1 1 2 2