CF713B.Searching Rectangles

Filya just learned new geometry object — rectangle. He is given a field consisting of n × n unit cells. Rows are numbered from bottom to top with integer from 1 to n. Columns are numbered from left to right with integers from 1 to n. Cell, located at the intersection of the row r and column c is denoted as (r, c). Filya has painted two rectangles, such that their sides are parallel to coordinate axes and each cell lies fully inside or fully outside each of them. Moreover, no cell lies in both rectangles.

Later, hedgehog Filya became interested in the location of his rectangles but was unable to find the sheet of paper they were painted on. They were taken by Sonya and now she wants to play a little game with Filya. He tells her a query rectangle and she replies with the number of initial rectangles that lie fully inside the given query rectangle. The query rectangle should match the same conditions as initial rectangles. Rectangle lies fully inside the query if each o its cells lies inside the query.

Filya knows Sonya really well, so is sure that if he asks more than 200 questions she will stop to reply.

菲利娅刚刚学习了一个新的几何对象——矩形。他得到了一个由 $n \times n$ 个单位格子组成的方阵。行从下到上依次编号为 $1$ 到 $n$，列从左到右依次编号为 $1$ 到 $n$。位于第 $r$ 行与第 $c$ 列交叉处的格子记作 $(r,\,c)$。菲利娅画了两个矩形，它们的边均与坐标轴平行，且每个格子要么完全位于某个矩形内部，要么完全位于其外部。此外，不存在任何一个格子同时属于这两个矩形。

后来，刺猬菲利娅开始关心自己所画矩形的位置，却找不到当初画它们的那张纸——这张纸被索尼娅拿走了。现在索尼娅想和菲利娅玩一个小游戏：菲利娅向她提出一个查询矩形（该矩形也需满足与初始矩形相同的条件：边与坐标轴平行，且每个格子要么完全在矩形内、要么完全在外），索尼娅则回答完全位于该查询矩形内部的初始矩形的个数。一个矩形“完全位于”查询矩形内部，当且仅当它的每一个格子都位于查询矩形内部。

菲利娅对索尼娅非常了解，因此他确信：如果他提出的询问次数超过 $200$ 次，索尼娅将拒绝继续回答。

The first line of the input contains an integer n (2 ≤ n ≤ 216) — size of the field.

For each query an integer between 0 and 2 is returned — the number of initial rectangles that lie fully inside the query rectangle.

输入的第一行包含一个整数 $n$（$2 \leq n \leq 2^{16}$）—— 表示场地的大小。

对于每个查询，返回一个介于 $0$ 到 $2$ 之间的整数——即完全位于查询矩形内部的初始矩形的个数。

To make a query you have to print "? _x_1 _y_1 _x_2 _y_2" (without quotes) (1 ≤ _x_1 ≤ _x_2 ≤ n, 1 ≤ _y_1 ≤ _y_2 ≤ n), where (_x_1, _y_1) stands for the position of the bottom left cell of the query and (_x_2, _y_2) stands for the up right cell of the query. You are allowed to ask no more than 200 queries. After each query you should perform "flush" operation and read the answer.

In case you suppose you've already determined the location of two rectangles (or run out of queries) you should print "! _x_11 _y_11 _x_12 _y_12 _x_21 _y_21 _x_22 _y_22" (without quotes), where first four integers describe the bottom left and up right cells of the first rectangle, and following four describe the corresponding cells of the second rectangle. You can print the rectangles in an arbitrary order. After you have printed the answer, print the end of the line and perform "flush". Your program should terminate immediately after it print the answer.

要提出一个查询，你需要输出 "? _x_1 _y_1 _x_2 _y_2"（不带引号），其中满足 1 ≤ _x_1 ≤ _x_2 ≤ _n 且 1 ≤ _y_1 ≤ _y_2 ≤ _n；(_x_1, _y_1) 表示该查询区域左下角单元格的位置，(_x_2, _y_2) 表示该查询区域右上角单元格的位置。你最多可进行 200 次查询。每次查询后，你必须执行“刷新（flush）”操作，并读取反馈结果。

当你认为自己已确定两个矩形的位置（或查询次数已用尽）时，应输出 "! _x_11 _y_11 _x_12 _y_12 _x_21 _y_21 _x_22 _y_22"（不带引号），其中前四个整数描述第一个矩形的左下角和右上角单元格，后四个整数描述第二个矩形的对应单元格。两个矩形的输出顺序可以任意。在输出答案后，请换行并执行“刷新（flush）”操作。你的程序应在输出答案后立即终止。