9S is on a special mission to locate all hidden mines in an abandoned airport. The airport is represented as an $$$N$$$ × $$$N$$$ grid, where $$$N$$$ is an odd integer. The rows are numbered from $$$1$$$ to $$$n$$$ from top to bottom, and the columns are numbered from $$$1$$$ to $$$n$$$ from left to right. Each cell $$$(i, j)$$$ represents the position at the $$$i$$$-th row and $$$j$$$-th column. There are $$$M$$$ hidden mines in the grid, and each mine emits a unique type of radiation.
To detect the mines, 9S uses a special drone that can sense radiation. The drone follows a specific spiral movement pattern, starting at the top-left corner $$$(1,1)$$$, facing right. It moves according to the following rules:
As the drone moves, it registers the radiation detected in each visited cell. The detected radiation is represented as a binary array of length $$$M$$$. If the $$$i$$$-th bit of this array is $$$1$$$, it means that the drone detected radiation from the $$$i$$$-th mine in that cell; otherwise, it is $$$0$$$.
A mine located at $$$(i_m, j_m)$$$ emits radiation to all cells in the same row or column, meaning that at a cell $$$(i_p, j_p)$$$, the drone will detect its radiation if and only if:
To avoid suspicion from the evil machines, 9S limits communication with the drone. The drone will only send data when it is positioned at specific cells that satisfy either of the following conditions:
When the drone is at one of these cells, it compresses the unsent data before sending it. The compression works as follows:
Given the list of compressed data that the drone sent after completing its journey, your task is to help 9S determine the exact locations of the $$$M$$$ mines.
The first line contains two integers $$$N$$$ and $$$M$$$ $$$(1 \le N \le 1001; 1 \le M \le 1000)$$$ — the size of the matrix and the number of mines in the grid.
The next $$$2N - 1$$$ lines each contain a binary string of length $$$M$$$, representing the compressed data that the drone sent to 9S each time he requested the data.
Print $$$M$$$ lines. The $$$i$$$-th line must contain two integers $$$r$$$ and $$$c$$$, where $$$r$$$ is the row where the $$$i$$$-th mine is located and $$$c$$$ is the column where the mine is located.
3 3000100100011010
1 3 3 1 3 2
1 3000
1 1 1 1 1 1
5 5000000000000000100101000100000000100000000000
5 1 3 3 3 3 5 4 3 1
| Name |
|---|


