This is a run-twice (communication) problem.

There are two players: Player A and Player B. The jury will first interact with player A. After player A ends their interaction, the jury will interact with player B. Note that player A and player B may not directly pass information to each other; both players are only able to send information or receive information from the jury, but they may agree on the strategy they will use to communicate.

The jury has a binary grid $$$G$$$ of $$$n$$$ rows and $$$n$$$ columns (each cell of this grid has value either $$$0$$$ or $$$1$$$). Row $$$1$$$ is the top-most row, and column $$$1$$$ is the left-most column. The connectivity of this grid is defined as $$$1$$$ if there is a path going left, right, up, or down going through only cells with value $$$1$$$ connecting each pair of cells $$$(i_1,j_1)$$$ and $$$(i_2,j_2)$$$ with $$$G_{i_1,j_1}=G_{i_2,j_2}=1$$$. Note that moving diagonally is not allowed. It is guaranteed that there exists at least one cell with value of $$$1$$$ in this grid.

The jury first interacts with player A. The jury will give player A the grid $$$G$$$. After inspecting the grid, player A must determine two integers $$$r$$$ and $$$c$$$ and send them to the jury. At the start of player B's interaction, player B will receive the values of all cells in the $$$r$$$'th row and all cells in the $$$c$$$'th column from the jury. Note that player B is not given the values of $$$r$$$ and $$$c$$$.

Player A wants to ensure player B can determine the connectivity of $$$G$$$. Your task is to act as both players and find a strategy so that player B is able to determine the connectivity correctly. Note that the communicator of this task is not adaptive – that is, the grid given to you on the first run will be the same as the grid used to evaluate the connectivity.

Input

Your code will be ran exactly two times on each test. On the first run, you will be Player A, and on the second Player B.

First Run Input

The first line of the input contains the string first. The purpose of this is so your program recognizes that this is its first run, and it should act as Player A.

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$C$$$ ($$$2 \leq n \leq 1000, 0 \leq C \leq 1$$$) – the size of the grid and the connectivity respectively.

The following $$$n$$$ lines contain information about the grid. The $$$i$$$th of these lines contains a binary string $$$G_i$$$ of length $$$n$$$, indicating the $$$i$$$-th row of the grid.

It is guaranteed that:

The sum of $$$n^2$$$ does not exceed $$$2\cdot 10^6$$$ over all test cases
The value of $$$C$$$ matches with the information in the grid – that is, if $$$C=1$$$, then the grid has connectivity $$$1$$$, and if $$$C=0$$$, then the grid has connectivity $$$0$$$.
Each grid has at least one $$$1$$$ in the input.

Second Run Input

The first line of the input contains the string second. The purpose of this is so your program recognizes that this is its second run, and it should act as Player B.

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows. Note that this number is equal to $$$t$$$ from the first run input.

The first line of each test case contains exactly one integer $$$n$$$ — the size of the grid given on the $$$i$$$'th test case of the first run input.

The second line of each test case contains a binary string $$$G_{r, 1}G_{r, 2}\ldots G_{r, n}$$$ — the contents in row $$$r$$$ of the grid. Note that the integer $$$r$$$ is sent by player A to the jury at the end of their interaction of the $$$i$$$'th test case

The third line of each test case contains a binary string $$$G_{1, c}G_{2, c}\ldots G_{n, c}$$$ — the contents in column $$$c$$$ of the grid. Note that the integer $$$c$$$ is sent by player A to the jury at the end of their interaction of the $$$i$$$'th test case.

Hacks

To make hacks, use the following format:

The first line should contain exactly one integer $$$t$$$ $$$(1 \le t \le 10^4)$$$ — the number of grids. Then, $$$t$$$ blocks of input should follow.

The first line of each block of input must contain a single integer $$$n$$$ $$$(2 \le n \le 1000)$$$ — the size of the grid the jury will choose.

Each of the next $$$n$$$ lines should contain a binary string of size $$$n$$$. The $$$i$$$'th of these lines should contain $$$G_{i, 1}G_{i, 2}\ldots G_{i, n}$$$ — the contents of the $$$i$$$'th row of the grid the jury will choose.

There must exist at least a single cell with value of $$$1$$$ in each grid, and the sum of $$$n^2$$$ over all test cases should not exceed $$$2\cdot 10^6$$$.

Note that the connectivity of each grid is determined by the jury, and you do not need to output it for a hack.

Output

For the first run, for each test case, output two integers $$$r$$$ and $$$c$$$ ($$$1 \leq r,c \leq n$$$). This indicates that you want the second run to receive the $$$r$$$-th row and the $$$c$$$-th column of the grid.

For the second run, for each test case, output an integer $$$C$$$ ($$$0 \leq C \leq 1$$$) – the connectivity of the grid.

Note

On the first input example, the first grid is the following:

1	1
1	0

On the first run, we know that $$$n = 2$$$. After inspecting the example, we can determine that the connectivity is $$$1$$$.

For the sake of this example, suppose Player A and Player B have agreed to some strategy where if the connectivity is $$$1$$$, then player A should send a row and a column that both end with $$$0$$$. In this case, row $$$2$$$ and column $$$2$$$ satisfies this strategy. Note that this is an example strategy for the sake of demonstration, and using this strategy will not work for all cases.

Then, take a look at the second run. Now, we are Player B. We receive that $$$n = 2$$$ and that the chosen row has values $$$r = [1, 0]$$$ and the chosen column has values $$$c = [1, 0]$$$. Since the last number of each row is $$$0$$$, player B uses the agreed upon strategy to determine that the connectivity is $$$1$$$.

Plegma

Examples