CF2255C.Even If the World Turns

Now, no matter what anyone says, I am the happiest girl in the world.

— Chtholly

This is a run-twice (communication) problem.

At the Fairy Warehouse, Nygglatho prepared an unusual game for Chtholly and Willem.

They would be separated and unable to exchange a single word. Between them there would be only a black-and-white picture — one that Nygglatho could shift, rotate, reflect, or even invert its colors.

Nygglatho saw it as a test of how well they understood each other. Chtholly and Willem perhaps saw only another kind of promise. No matter how the world turned, they would still find the same place.

The two players are Chtholly and Willem. The jury, acting as Nygglatho, first communicates with Chtholly. After Chtholly finishes, the jury communicates with Willem. Chtholly and Willem may agree on the strategy they will use beforehand, but they cannot directly pass information to each other.

In each test case, Nygglatho prepares a black-and-white picture consisting of $n \times n$ cells and chooses a target cell $x$. The rows and columns are numbered from $1$ to $n$.

The picture contains $w$ black cells. It is guaranteed that $\gcd(n,w)=1$.

Nygglatho first shows the picture and the target cell $x$ to Chtholly. Chtholly must choose two cells and swap their colors. The two cells are allowed to be the same. If they are the same, or if they have the same color, the picture does not change. She cannot send Willem any other information.

Swapping colors does not move the target cell.

Nygglatho then secretly transforms the picture. She may perform the following operations any number of times, possibly zero, in any order:

1. Choose two integers $d_r$ and $d_c$ ($0\le d_r,d_c \lt n$) and cyclically shifts the picture. Every cell $(r,c)$ moves to $\left(\left(r-1+d_r\right)\bmod n+1,\left(c-1+d_c\right)\bmod n+1\right)$;
2. Rotate the picture clockwise by $90^\circ$. One such rotation moves every cell $(r,c)$ to $(c,n+1-r)$;
3. Reflect the picture across its vertical axis. Such a reflection moves every cell $(r,c)$ to $(r,n+1-c)$;
4. Invert all colors. This changes every black cell into a white cell and every white cell into a black cell.

The target cell $x$ undergoes every cyclic shift, rotation, and reflection in exactly the same way as the picture. Color inversions do not move it.

Finally, Nygglatho shows only the resulting picture to Willem. Willem must determine the final position of $x$.

Your program will be run exactly twice on each test. On the first run, it must act as Chtholly. On the second run, it must act as Willem. No information is preserved between the two runs except for the information passed by the jury according to the rules above.

The order of the test cases may be changed between the two runs.

First Run

On the first run, you are Chtholly.

Input

The first line contains the string first, indicating that this is the first run.

After this line, the remaining input has the following format.

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 an integer $n$ ($2 \le n \le 800$) — the height and width of the picture.

Each of the next $n$ lines contains a string of length $n$. The character $\mathtt{\#}$ denotes a black cell, and the character $\mathtt{.}$ denotes a white cell.

The next line contains two integers $r_x$ and $c_x$ ($1 \le r_x,c_x \le n$) — the row and column of the target cell $x$.

Let $w$ be the number of black cells in the picture. It is guaranteed that $\gcd(n,w)=1$.

It is guaranteed that the sum of $n^2$ over all test cases does not exceed $800^2$.

Output

For each test case, output four integers $r_1$, $c_1$, $r_2$, and $c_2$ ($1 \le r_1,c_1,r_2,c_2 \le n$) — the two cells whose colors Chtholly chooses to swap. The two cells are allowed to be the same.

Second Run

On the second run, you are Willem.

Input

The first line contains the string second, indicating that this is the second run.

After this line, the remaining input has the following format.

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 value of $t$ is the same as on the first run, although the test cases may appear in a different order.

The first line of each test case contains the integer $n$ ($2 \le n \le 800$).

Each of the next $n$ lines contains a string of length $n$, describing the resulting picture after Chtholly's swap and Nygglatho's transformations for the corresponding test case from the first run. Again, $\mathtt{\#}$ denotes a black cell and $\mathtt{.}$ denotes a white cell.

It is guaranteed that the sum of $n^2$ over all test cases does not exceed $800^2$.

Output

For each test case, output two integers $r'_x$ and $c'_x$ ($1 \le r'_x,c'_x \le n$) — the row and column of the target cell after all transformations.

Hacks are disabled in this problem.

现在，无论别人怎么说，我都是世界上最幸福的女孩。

—— 莉莉安

本题为“运行两次”（通信）类题目。

在妖精仓库中，尼古拉托为莉莉安与威廉准备了一场别开生面的游戏。

他们将被分隔开来，彼此之间无法交换只言片语。两人之间仅有一幅黑白图像——而这幅图像可由尼古拉托任意平移、旋转、镜像翻转，甚至反转所有颜色。

尼古拉托视其为对二人默契程度的一场考验；而莉莉安与威廉或许只将其看作另一种承诺：无论世界如何变幻，他们终将在同一处重逢。

两名玩家分别为莉莉安与威廉。裁判扮演尼古拉托的角色，首先与莉莉安通信；莉莉安完成操作后，裁判再与威廉通信。莉莉安与威廉可在赛前约定策略，但彼此之间无法直接传递任何信息。

在每个测试用例中，尼古拉托准备一幅 $n \times n$ 的黑白图像，并选定一个目标格子 $x$。行与列均从 $1$ 编号至 $n$。

该图像包含 $w$ 个黑色格子。保证 $\gcd(n,w)=1$。

尼古拉托首先向莉莉安展示该图像及目标格子 $x$。莉莉安必须选择两个格子并交换它们的颜色（允许选择同一格子；若所选两格相同或颜色相同，则图像不变）。她不能向威廉传递任何其他信息。

交换颜色的操作不会移动目标格子 $x$。

随后，尼古拉托秘密地对该图像执行若干次（可能为零次）如下变换，顺序与次数任意：

1. 选取两个整数 $d_r$ 和 $d_c$（满足 $0\le d_r,d_c \lt n$），对图像进行循环平移：每个格子 $(r,c)$ 移动至 $\left(\left(r-1+d_r\right)\bmod n+1,\left(c-1+d_c\right)\bmod n+1\right)$；
2. 将图像顺时针旋转 $90^\circ$：一次旋转使每个格子 $(r,c)$ 移动至 $(c,n+1-r)$；
3. 沿图像的竖直中轴线作镜像反射：该反射使每个格子 $(r,c)$ 移动至 $(r,n+1-c)$；
4. 反转所有格子的颜色：每个黑格变为白格，每个白格变为黑格。

目标格子 $x$ 会以与图像完全相同的方式经历每一次循环平移、旋转和镜像反射；颜色反转不改变其位置。

最后，尼古拉托仅将变换后的图像展示给威廉。威廉必须确定 $x$ 在最终图像中的位置。

你的程序将在每个测试用例上恰好运行两次：第一次作为莉莉安，第二次作为威廉。除按上述规则经裁判传递的信息外，两次运行之间不保留任何其他信息。

两次运行中测试用例的顺序可能不同。

第一次运行

在第一次运行中，你扮演莉莉安。

输入

第一行为字符串 first，表示这是第一次运行。

此后输入格式如下：

每个测试包含多个测试用例。第一行包含测试用例数量 $t$（$1 \le t \le 10^4$），随后是各测试用例的描述。

每个测试用例的第一行为整数 $n$（$2 \le n \le 800$）——图像的高与宽。

接下来 $n$ 行，每行一个长度为 $n$ 的字符串。字符 $\mathtt{\#}$ 表示黑格，字符 $\mathtt{.}$ 表示白格。

下一行包含两个整数 $r_x$ 和 $c_x$（$1 \le r_x,c_x \le n$）——目标格子 $x$ 的行号与列号。

记图像中黑格数量为 $w$，保证 $\gcd(n,w)=1$。

保证所有测试用例的 $n^2$ 之和不超过 $800^2$。

输出

对每个测试用例，输出四个整数 $r_1$, $c_1$, $r_2$, $c_2$（$1 \le r_1,c_1,r_2,c_2 \le n$）——莉莉安选择交换颜色的两个格子的坐标。允许两格相同。

第二次运行

在第二次运行中，你扮演威廉。

输入

第一行为字符串 second，表示这是第二次运行。

此后输入格式如下：

每个测试包含多个测试用例。第一行包含测试用例数量 $t$（$1 \le t \le 10^4$），随后是各测试用例的描述。

此处的 $t$ 值与第一次运行中相同，但测试用例的顺序可能不同。

每个测试用例的第一行为整数 $n$（$2 \le n \le 800$）。

接下来 $n$ 行，每行一个长度为 $n$ 的字符串，描述对应第一次运行中测试用例经莉莉安交换颜色及尼古拉托变换后所得的最终图像。其中 $\mathtt{\#}$ 表示黑格，$\mathtt{.}$ 表示白格。

保证所有测试用例的 $n^2$ 之和不超过 $800^2$。

输出

对每个测试用例，输出两个整数 $r'_x$ 和 $c'_x$（$1 \le r'_x,c'_x \le n$）——目标格子 $x$ 经全部变换后所在位置的行号与列号。

本题禁用 Hack。

null

null

The first example shows Chtholly's run for two test cases. The second example shows Willem's run for the same two test cases. The outputs shown for Chtholly's run are just one possible set of valid choices.

In the first test case, Chtholly swaps cells $(1,1)$ and $(4,1)$. Afterwards, the two black cells are at $(2,2)$ and $(4,1)$.

In this example, Nygglatho performs the following transformations.

• she cyclically shifts the picture one row down and two columns to the right;
• she rotates the picture clockwise by $90^\circ$ once;
• she reflects the picture across its vertical axis;

The target moves from $(3,4)$ to $(4,1)$ after the cyclic shift, then to $(1,2)$ after the rotation, and finally to $(1,4)$ after the reflection. The two black cells finally arrive at $(3,5)$ and $(4,3)$, giving exactly the picture in Willem's run. Willem reports the target position $(1,4)$.

In the second test case, Chtholly can choose the same cell, in which case nothing changes. Nygglatho can then also choose to do nothing.

第一个示例展示了Chtholly在两个测试用例中的运行过程。第二个示例展示了Willem在相同两个测试用例中的运行过程。Chtholly运行所显示的输出仅为一组可能的有效选择。

在第一个测试用例中，Chtholly交换了单元格 $(1,1)$ 和 $(4,1)$。之后，两个黑格分别位于 $(2,2)$ 和 $(4,1)$。

在此示例中，Nygglatho执行了以下变换：

• 将图像循环下移一行、右移两列；
• 将图像顺时针旋转 $90^\circ$ 一次；
• 将图像沿其竖直轴进行反射；

目标点从 $(3,4)$ 出发，在循环移位后到达 $(4,1)$，再经旋转到达 $(1,2)$，最后经反射到达 $(1,4)$。两个黑格最终到达 $(3,5)$ 和 $(4,3)$，恰好得到Willem运行中的图像。Willem报告的目标位置为 $(1,4)$。

在第二个测试用例中，Chtholly可以选择同一个单元格，此时图像不发生任何变化。Nygglatho随后也可选择不做任何操作。