I. Mine sweeper
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

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:

  1. If the cell in front has not been visited, the drone moves forward.
  2. If the cell in front has been visited or there is no cell ahead (because it is at the edge), the drone turns $$$90^\circ$$$ clockwise and tries to move forward again.
  3. The process continues until every cell in the grid has been visited exactly once.

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:

$$$i_p = i_m$$$ or $$$j_p = j_m$$$

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:

$$$i_p = j_p$$$ or $$$i_p + j_p = N + 1$$$

When the drone is at one of these cells, it compresses the unsent data before sending it. The compression works as follows:

  1. The drone computes the bitwise AND of all previously recorded readings that have not yet been sent.
  2. It then sends the resulting binary array to 9S.
  3. The reading of the current cell itself is not included in the compression.
  4. If there is no unsent data, the drone sends an array where all bits are set to $$$0$$$.

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.

Input

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.

Output

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.

Examples
Input
3 3
000
100
100
011
010
Output
1 3
3 1
3 2
Input
1 3
000
Output
1 1
1 1
1 1
Input
5 5
00000
00000
00000
10010
10001
00000
00010
00000
00000
Output
5 1
3 3
3 3
5 4
3 1