这是一个交互式问题。

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

科学家们正试图了解海狸大坝的结构。他们已经确定了它的布局——确切地知道哪些相邻网格之间有通道。还已知通道构成的图是一棵树——这意味着任何两个网格之间都有且仅有一条通过通道的路径，且每个网格最多只被访问一次。不幸的是，科学家们还无法了解太多关于出口的信息——他们只知道 $k \ge 1$，这意味着大坝中至少有一个出口。

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

实验过程如下。科学家们将两只海狸分别放入矩形大坝的网格 $(i_1, j_1)$ 和 $(i_2, j_2)$ 中。之后，每只海狸都会通过通道游向最近的出口。一切发生得非常快，因此科学家只能确定哪只海狸更快到达出口。如果两只海狸同时到达出口，实验结果是未定义的——这意味着第一只或第二只海狸都有可能先到达。

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

交互

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

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

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

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

然后，你的程序与裁判程序进行交互，进行查询并接收实验结果。你最多可以执行 $48$ 次题目描述中说明的查询操作。

要进行询问，请输出格式为 ? i1 j1 i2 j2 的字符串，之后 $2$ 只海狸将被放入大坝的指定点 $(i_1, j_1)$ 和 $(i_2, j_2)$。必须满足条件 $1 \le i_1, i_2 \le n$ 且 $1 \le j_1, j_2 \le m$。

作为响应，裁判程序会输出：

• 1，如果第一只海狸到达出口的时间不晚于第二只海狸；
• 2，如果第二只海狸到达出口的时间不晚于第一只海狸；
• 如果海狸同时到达出口，则输出上述两个判定中的任意一个。

要输出问题的答案，请输出字符串 ! i j，其中 $i$ 和 $j$ 应为其中一个出口所在的行号和列号。此输出不计入查询次数。如果大坝中有多个出口，你可以输出其中任意一个。之后，交互器将输出判定——如果你的猜测正确，则输出 Win，否则输出 Lose。如果你的答案不正确，你的程序将获得 WA（Wrong Answer）判定并终止。为了避免获得不正确的判定，如果你的程序收到输出答案不正确的信息，也应当立即终止。

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

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

在你的程序的每次操作之后，请清空（flush）输出流。

如果你在 Pascal 中使用 writeln，在 C++ 中使用 cout << ... << endl，在 Java 中使用 System.out.println，在 Python 中使用 print，在 C# 中使用 Console.WriteLine，则输出流会自动清空，不需要额外操作。如果你使用其他输出方法，建议手动清空输出流。

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

样例

输入样例 1

2 3
10
01
111

1

2

1

2

Win

输出样例 1

? 1 1 1 2

? 1 3 2 1

? 1 2 2 3

? 1 2 2 3

! 2 2

说明

在题目的样例中，迷宫如下所示：

也就是说，大坝的出口位于点 $(1, 1)$ 和 $(2, 2)$。