CF1153E.Serval and Snake

This is an interactive problem.

Now Serval is a senior high school student in Japari Middle School. However, on the way to the school, he must go across a pond, in which there is a dangerous snake. The pond can be represented as a $n \times n$ grid. The snake has a head and a tail in different cells, and its body is a series of adjacent cells connecting the head and the tail without self-intersecting. If Serval hits its head or tail, the snake will bite him and he will die.

Luckily, he has a special device which can answer the following question: you can pick a rectangle, it will tell you the number of times one needs to cross the border of the rectangle walking cell by cell along the snake from the head to the tail. The pictures below show a possible snake and a possible query to it, which will get an answer of $4$.

Today Serval got up too late and only have time to make $2019$ queries. As his best friend, can you help him find the positions of the head and the tail?

Note that two cells are adjacent if and only if they have a common edge in the grid, and a snake can have a body of length $0$, that means it only has adjacent head and tail.

Also note that the snake is sleeping, so it won't move while Serval using his device. And what's obvious is that the snake position does not depend on your queries.

这是一个交互式问题。

现在，Serval 是加帕里中学的一名高中生。然而，在上学途中，他必须穿过一个池塘，而池塘中有一条危险的蛇。该池塘可表示为一个 $n \times n$ 的网格。蛇有一个头部和一个尾部，分别位于不同的格子中；其身体是由一系列相邻格子构成的、连接头与尾的一条不自交路径。若 Serval 踩到蛇的头部或尾部，蛇便会咬他，导致他死亡。

幸运的是，他拥有一种特殊装置，可以回答如下问题：你可以选定一个矩形区域，该装置将返回——从蛇头出发、沿蛇身逐格走向蛇尾的过程中，穿越该矩形边界的次数。下方图片展示了一条可能的蛇以及对它的一次查询示例，该查询的答案为 $4$。

今天 Serval 起得太晚，仅有时间进行 $2019$ 次查询。作为他最好的朋友，你能否帮他找出蛇头和蛇尾的位置？

注意：当且仅当两个格子在网格中拥有公共边时，它们才被视为相邻；蛇的身体长度可以为 $0$，即此时蛇头与蛇尾处于相邻格子中。

另外请注意：蛇正在睡觉，因此在 Serval 使用该装置期间不会移动；显然，蛇的位置与你的查询无关。

The first line contains a single integer $n$ ($2\leq n \leq 1000$) — the size of the grid.

第一行包含一个整数 $n$（$2\leq n \leq 1000$）——网格的大小。

When you are ready to answer, you should print ! x1 y1 x2 y2, where $(x_1, y_1)$ represents the position of the head and $(x_2,y_2)$ represents the position of the tail. You can print head and tail in any order.

当你准备好回答时，你应该输出 ! x1 y1 x2 y2，其中 $(x_1, y_1)$ 表示头部的位置，$(x_2, y_2)$ 表示尾部的位置。头部和尾部的顺序可以任意。

The pictures above show our queries and the answers in the first example. We first made a query for $(1,1)$ and got an answer $1$, then found that it must be connected to exactly one other cell. Then we made a query for $(1,2)$ and got an answer of $0$, then knew that the snake never entered it. So the cell connected to $(1,1)$ must be $(2,1)$. Then we made a query for $(2,2)$ and got an answer $0$, then knew that it never entered $(2,2)$ as well. So the snake cannot leave $(2,1)$, which implies that the answer is $(1,1)$ and $(2,1)$.

The pictures above show our queries and the answers in the second example. By making query to $(2,2)$ and receiving $2$, we found that the snake occupies $(2,2)$. And by making query to rectangle from $(2,1)$ to $(2,3)$ and receiving answer $0$, we knew that it never goes out of the rectangle from $(2,1)$ to $(2,3)$. Since the first answer is $2$, both $(2,1)$ and $(2,3)$ must be occupied but none of others, so the answer is $(2,1)$ and $(2,3)$.

上图展示了第一个样例中的查询过程及其对应答案。我们首先对单元格 $(1,1)$ 发起查询，得到答案 $1$，由此推断该单元格恰好与另一个单元格相连。接着，我们对 $(1,2)$ 发起查询，得到答案 $0$，从而得知蛇从未进入该单元格。因此，与 $(1,1)$ 相连的单元格必为 $(2,1)$。随后，我们对 $(2,2)$ 发起查询，得到答案 $0$，从而确认蛇也从未进入 $(2,2)$。因此，蛇无法离开 $(2,1)$，最终可确定蛇占据的两个单元格为 $(1,1)$ 和 $(2,1)$。

上图展示了第二个样例中的查询过程及其对应答案。通过对 $(2,2)$ 发起查询并得到答案 $2$，我们得知蛇占据了 $(2,2)$；而通过对矩形区域 $(2,1)$ 到 $(2,3)$ 发起查询并得到答案 $0$，我们得知蛇从未离开该矩形区域。由于第一次查询结果为 $2$，说明 $(2,1)$ 和 $(2,3)$ 均被占据，其余单元格均未被占据，因此答案为 $(2,1)$ 和 $(2,3)$。