说明

这是一个交互题。

海狸水坝是一个由 $n \times m$ 个单元格组成的矩形，某些相邻单元格之间有秘密通道，海狸可以利用这些通道移动。水坝有 $k$ 个出口——即矩形中那些可以游出水坝的单元格。

科学家们试图弄清楚海狸水坝的结构。他们已经确定了其布局——确切地知道哪些相邻单元格之间有通道。同时已知，通道图构成了一棵树——这意味着任意两个单元格之间通过通道存在唯一路径，且每个单元格在路径中最多经过一次。不幸的是，科学家们目前对出口知之甚少——他们只知道 $k \geq 1$，即至少有一个出口。

为了找到水坝的出口，科学家们决定使用实验海狸。海狸是聪明的动物，它们完全了解自己水坝的布局，包括所有出口的位置。由于科学家们只剩下少数海狸可用于实验，他们最多只能进行 $48$ 次实验。

实验过程如下。科学家取出两只海狸，将它们分别释放到矩形水坝的单元格 $(i_1, j_1)$ 和 $(i_2, j_2)$ 中。之后，每只海狸将通过通道游向最近的出口。一切发生得非常快，因此科学家们只能确定哪只海狸先到达出口。如果两只海狸同时到达出口，则实验结果不确定——即可能是第一只先到，也可能是第二只先到。

科学家们需要从内部研究海狸水坝，因此他们需要发现至少一个水坝的出口。请帮助他们找到它。

交互协议

开始时，你的程序需要读取测试参数。

第一行包含两个整数 $n$、$m$——水坝的尺寸（$2 \leq n, m \leq 10^6$； $4 \leq n \cdot m \leq 10^6$）。

接下来的 $n$ 行包含字符串 $h_i$，长度为 $m - 1$，由 $0$ 和 $1$ 组成，描述水坝中的水平通道：如果 $h_{i,j}=1$，则在单元格 $(i, j)$ 和 $(i, j+1)$ 之间存在直接通道。

接下来的 $n-1$ 行包含字符串 $v_i$，长度为 $m$，由 $0$ 和 $1$ 组成，描述水坝中的垂直通道：如果 $v_{i,j}=1$，则在单元格 $(i, j)$ 和 $(i+1, j)$ 之间存在直接通道。

然后，你的程序开始与评测程序交互，进行查询并接收实验结果。你可以执行题目描述中所述的操作，最多不超过 $48$ 次。

要提出询问，请输出格式为 <<? $i_1$ $j_1$ $i_2$ $j_2$>> 的字符串，之后两只海狸将被释放到水坝中指定的点 $(i_1, j_1)$ 和 $(i_2, j_2)$。必须满足 $1 \leq i_1, i_2 \leq n$； $1 \leq j_1, j_2 \leq m$ 的条件。

作为回应，评测程序将输出：

• $1$，如果第一只海狸不晚于第二只海狸到达出口；
• $2$，如果第二只海狸不晚于第一只海狸到达出口；
• 如果海狸同时到达出口，则输出以上两种结果中的任意一种。

要输出问题的答案，请输出字符串 $\tt{!\ i\ j}$，其中 $i$ 和 $j$ 应该是某个出口所在的行号和列号。此输出不计入查询次数。如果水坝有多个出口，你可以输出其中任意一个。之后，交互器将输出一个判定结果——如果你的猜测正确，则为 $\texttt{Win}$，否则为 $\texttt{Lose}$。如果你的答案不正确，你的解法将收到 $\texttt{WA}$（答案错误）的判定并终止。为避免收到不正确的判定，如果你的程序收到信息表明输出的答案不正确，它也应该终止。

如果在任何时候你的程序超过了 $48$ 次查询的限制，你的程序将因 $\texttt{WA}$ 判定而终止。

在你的程序每次输出后，输出一个换行符。

在你的程序每次输出后，刷新输出流。

请注意，在此问题中，交互器可能是自适应的，这意味着迷宫的状态始终与已进行的查询一致，但在执行过程中可能会发生变化。

2 3
10
01
111

1

2

1

2

Win

? 1 1 1 2

? 1 3 2 1

? 1 2 2 3

? 1 2 2 3

! 2 2

提示

在样例交互中，评测程序和参赛者程序之间的消息用空行分隔，以便直观显示哪个消息是对哪个消息的响应。在实际交互中，不会有空行，你也不应打印任何空行。

在题目描述的示例中，迷宫如图所示：

:::align{center} :::

即，水坝的出口位于点 $(1, 1)$ 和 $(2, 2)$。

翻译由 DeepSeek 完成