CF2255C Even If the World Turns

:::epigraph[— Chtholly] 现在，无论别人怎么说，我都是世界上最幸福的女孩。 ::: 这是一个需要运行两次（通信）的题目。 在精灵仓库里，Nygglatho 为 Chtholly 和 Willem 准备了一个不同寻常的游戏。 他们将被分开，无法交流任何一个字。两人之间只有一张黑白图片——而 Nygglatho 可以对其进行平移、旋转、翻转，甚至反色。 Nygglatho 将它视为考验彼此理解程度的测试。而 Chtholly 和 Willem 也许只把它当成另一种约定。无论世界如何变化，他们都能找到同一个地方。 玩家是 Chtholly 和 Willem。裁判（模拟 Nygglatho 的身份）首先与 Chtholly 进行通信。在 Chtholly 完成后，裁判与 Willem 通信。Chtholly 和 Willem 可以事先商定策略，但不能彼此直接传递信息。 每组测试中，Nygglatho 会准备一张由 $n \times n$ 个格子组成的黑白图片，并选定一个目标格子 $x$。行和列编号从 $1$ 到 $n$。 图片包含 $w$ 个黑格，并且保证 $\gcd(n, w) = 1$。 Nygglatho 首先把图片和目标格子 $x$ 展示给 Chtholly。Chtholly 必须选择两个格子并交换它们的颜色。两个格子允许相同。若相同或颜色相同，则图片不会改变。她不能向 Willem 传递任何其他信息。 交换颜色不会移动目标格子。 随后 Nygglatho 会秘密地变换图片。她可以以任意次数、任意顺序执行以下操作（可以为零次）： 1. 选择两个整数 $d_r$ 和 $d_c$（$0 \le d_r, d_c < 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$ 会随着图片经历所有循环平移、旋转和翻转经过相同的变换。反色时不会移动目标格。 最后，Nygglatho 只把变换后的图片展示给 Willem。Willem 必须确定目标格 $x$ 的最终位置。 你的程序将在每组测试上被运行两次。第一次作为 Chtholly 执行，第二次作为 Willem 执行。除了上述规则允许的信息外，程序的两次执行之间不得保留任何信息。 测试用例在两次运行间的顺序可能会改变。 **第一次运行** 在第一次运行中，你是 Chtholly。 **输入** 第一行包含字符串 $\texttt{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$），即 Chtholly 选择交换颜色的两个格子。可以选择相同的格子。 **第二次运行** 在第二次运行中，你是 Willem。 **输入** 第一行包含字符串 $\texttt{second}$，表示当前为第二次运行。 接下来输入格式如下： 每组测试包含若干测试用例。第一行包含一个整数 $t$（$1 \le t \le 10^4$），为测试用例数。 $t$ 的值与第一次运行中相同，但测试用例顺序可能不同。 每个测试用例第一行包含一个整数 $n$（$2 \le n \le 800$）。 接下来的 $n$ 行，每行一个长度为 $n$ 的字符串，表示经过 Chtholly 的交换和 Nygglatho 所有变换后得到的图片。$\mathtt{\#}$ 表示黑格，$\mathtt{.}$ 表示白格。 保证所有测试用例的 $n^2$ 之和不超过 $800^2$。 **输出** 对于每个测试用例，输出两个整数 $r'_x$、$c'_x$（$1 \le r'_x,c'_x \le n$），即所有变换完毕后目标格 $x$ 的最终位置。 **本题禁用 Hack。**

无

无

第一个例子展示了 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 也可以选择什么都不做。 由 ChatGPT 5 翻译