English · Original
Chinese · Translation
Formal · Original
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.
## Input
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.
## Output
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.
[samples]
## Interaction
To flush you can use (just after printing an integer and end-of-line):
* _fflush(stdout)_ in C++;
* _System.out.flush()_ in Java;
* _stdout.flush()_ in Python;
* _flush(output)_ in Pascal;
* See the documentation for other languages.
You will get the _Wrong Answer_ verdict if you ask more than 200 queries, or if you print an incorrect coordinates.
You will get the _Idleness Limit Exceeded_ verdict if you don't print anything (but you should) or if you forget about flushing the output (more info below).
**Hacking.**
The first line should contain an integer _n_ (2 ≤ _n_ ≤ 216).
The second line should contain four integers _x_1, _y_1, _x_2, _y_2 (1 ≤ _x_1 ≤ _x_2 ≤ _n_, 1 ≤ _y_1 ≤ _y_2 ≤ _n_) — the description of the first rectangle.
The third line contains the description of the second rectangle in the similar way.
Filya 刚刚学习了一个新的几何对象——矩形。他被给定一个由 #cf_span[n × n] 个单位格子组成的场地。行从下到上用整数 #cf_span[1] 到 #cf_span[n] 编号，列从左到右用整数 #cf_span[1] 到 #cf_span[n] 编号。位于第 #cf_span[r] 行和第 #cf_span[c] 列交叉处的格子记为 #cf_span[(r, c)]。Filya 绘制了两个矩形，使得它们的边与坐标轴平行，且每个格子完全位于每个矩形的内部或外部。此外，没有格子同时属于两个矩形。
后来，刺猬 Filya 对他两个矩形的位置产生了兴趣，但找不到绘制它们的纸张。纸张被 Sonya 拿走了，现在她想和 Filya 玩一个小游戏。他告诉她一个查询矩形，她则回复有多少个初始矩形完全位于该查询矩形内。查询矩形必须满足与初始矩形相同的条件。一个矩形完全位于查询矩形内，当且仅当它的每个格子都位于查询矩形内。
Filya 非常了解 Sonya，所以他确信如果他问超过 #cf_span[200] 个问题，她就会停止回答。
输入的第一行包含一个整数 #cf_span[n] (#cf_span[2 ≤ n ≤ 216]) —— 场地的大小。
对于每个查询，返回一个介于 #cf_span[0] 和 #cf_span[2] 之间的整数 —— 完全位于查询矩形内的初始矩形的数量。
要进行一次查询，你必须打印 "_?_ #cf_span[x1] #cf_span[y1] #cf_span[x2] #cf_span[y2]"（不含引号）(#cf_span[1 ≤ x1 ≤ x2 ≤ n], #cf_span[1 ≤ y1 ≤ y2 ≤ n])，其中 #cf_span[(x1, y1)] 表示查询矩形的左下角格子，#cf_span[(x2, y2)] 表示查询矩形的右上角格子。你最多可以进行 #cf_span[200] 次查询。每次查询后，你必须执行 "flush" 操作并读取答案。
如果你认为已经确定了两个矩形的位置（或用完了查询次数），你应该打印 "_!_ #cf_span[x11] #cf_span[y11] #cf_span[x12] #cf_span[y12] #cf_span[x21] #cf_span[y21] #cf_span[x22] #cf_span[y22]"（不含引号），其中前四个整数描述第一个矩形的左下角和右上角格子，后四个整数描述第二个矩形的对应格子。你可以按任意顺序输出两个矩形。打印答案后，打印换行符并执行 "flush"。你的程序在打印答案后应立即终止。
要刷新输出，你可以在打印整数和换行符后使用：
如果你询问超过 #cf_span[200] 次查询，或打印了错误的坐标，你将获得 _Wrong Answer_ 结果。
如果你没有打印任何内容（但你应该打印），或忘记刷新输出，你将获得 _Idleness Limit Exceeded_ 结果（更多信息见下文）。
*黑客攻击*
第一行应包含一个整数 #cf_span[n] (#cf_span[2 ≤ n ≤ 216])。
第二行应包含四个整数 #cf_span[x1], #cf_span[y1], #cf_span[x2], #cf_span[y2] (#cf_span[1 ≤ x1 ≤ x2 ≤ n], #cf_span[1 ≤ y1 ≤ y2 ≤ n]) —— 第一个矩形的描述。
第三行以类似方式包含第二个矩形的描述。
## Input
输入的第一行包含一个整数 #cf_span[n] (#cf_span[2 ≤ n ≤ 216]) —— 场地的大小。对于每个查询，返回一个介于 #cf_span[0] 和 #cf_span[2] 之间的整数 —— 完全位于查询矩形内的初始矩形的数量。
## Output
要进行一次查询，你必须打印 "_?_ #cf_span[x1] #cf_span[y1] #cf_span[x2] #cf_span[y2]"（不含引号）(#cf_span[1 ≤ x1 ≤ x2 ≤ n], #cf_span[1 ≤ y1 ≤ y2 ≤ n])，其中 #cf_span[(x1, y1)] 表示查询矩形的左下角格子，#cf_span[(x2, y2)] 表示查询矩形的右上角格子。你最多可以进行 #cf_span[200] 次查询。每次查询后，你必须执行 "flush" 操作并读取答案。如果你认为已经确定了两个矩形的位置（或用完了查询次数），你应该打印 "_!_ #cf_span[x11] #cf_span[y11] #cf_span[x12] #cf_span[y12] #cf_span[x21] #cf_span[y21] #cf_span[x22] #cf_span[y22]"（不含引号），其中前四个整数描述第一个矩形的左下角和右上角格子，后四个整数描述第二个矩形的对应格子。你可以按任意顺序输出两个矩形。打印答案后，打印换行符并执行 "flush"。你的程序在打印答案后应立即终止。
[samples]
## Interaction
要刷新输出，你可以在打印整数和换行符后使用：
_fflush(stdout)_ 在 C++ 中；
_System.out.flush()_ 在 Java 中；
_stdout.flush()_ 在 Python 中；
_flush(output)_ 在 Pascal 中；
请参阅其他语言的文档。
如果你询问超过 #cf_span[200] 次查询，或打印了错误的坐标，你将获得 _Wrong Answer_ 结果。
如果你没有打印任何内容（但你应该打印），或忘记刷新输出，你将获得 _Idleness Limit Exceeded_ 结果（更多信息见下文）。
*黑客攻击*
第一行应包含一个整数 #cf_span[n] (#cf_span[2 ≤ n ≤ 216])。
第二行应包含四个整数 #cf_span[x1], #cf_span[y1], #cf_span[x2], #cf_span[y2] (#cf_span[1 ≤ x1 ≤ x2 ≤ n], #cf_span[1 ≤ y1 ≤ y2 ≤ n]) —— 第一个矩形的描述。
第三行以类似方式包含第二个矩形的描述。
**Definitions:**
- Let $ \mathcal{R}_1 = [x_{11}, x_{12}] \times [y_{11}, y_{12}] $ and $ \mathcal{R}_2 = [x_{21}, x_{22}] \times [y_{21}, y_{22}] $ be two axis-aligned rectangles on an $ n \times n $ grid, with integer coordinates satisfying $ 1 \le x_{ij} \le x_{ij}' \le n $, $ 1 \le y_{ij} \le y_{ij}' \le n $.
- $ \mathcal{R}_1 \cap \mathcal{R}_2 = \emptyset $: the rectangles are disjoint.
- A query rectangle $ Q = [a, b] \times [c, d] $ returns $ |\{ i \in \{1,2\} : \mathcal{R}_i \subseteq Q \}| \in \{0,1,2\} $.
**Given:**
- $ n \in \mathbb{Z} $, $ 2 \le n \le 216 $.
- Two disjoint axis-aligned rectangles $ \mathcal{R}_1, \mathcal{R}_2 $ on the grid $ \{1, \dots, n\}^2 $.
- Access to a black-box oracle that, given a query rectangle $ Q $, returns the number of $ \mathcal{R}_i $ fully contained in $ Q $.
- At most 200 queries allowed.
**Objective:**
Determine the coordinates $ (x_{11}, y_{11}, x_{12}, y_{12}) $ and $ (x_{21}, y_{21}, x_{22}, y_{22}) $ of $ \mathcal{R}_1 $ and $ \mathcal{R}_2 $, in any order, using at most 200 queries.
API Response (JSON)
{
"problem": {
"name": "B. Searching Rectangles",
"description": {
"content": "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 l",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 1000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF713B"
},
"statements": [
{
"statement_type": "Markdown",
"content": "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 l...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "Filya 刚刚学习了一个新的几何对象——矩形。他被给定一个由 #cf_span[n × n] 个单位格子组成的场地。行从下到上用整数 #cf_span[1] 到 #cf_span[n] 编号，列从左到右用整数 #cf_span[1] 到 #cf_span[n] 编号。位于第 #cf_span[r] 行和第 #cf_span[c] 列交叉处的格子记为 #cf_span[(r, c)]。Filya ...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions:**\n- Let $ \\mathcal{R}_1 = [x_{11}, x_{12}] \\times [y_{11}, y_{12}] $ and $ \\mathcal{R}_2 = [x_{21}, x_{22}] \\times [y_{21}, y_{22}] $ be two axis-aligned rectangles on an $ n \\times n $...",
"is_translate": false,
"language": "Formal"
}
]
}