CF1552H.Guess the Perimeter

Let us call a point of the plane admissible if its coordinates are positive integers less than or equal to $200$.

There is an invisible rectangle such that:

• its vertices are all admissible;
• its sides are parallel to the coordinate axes;
• its area is strictly positive.

Your task is to guess the perimeter of this rectangle.

In order to guess it, you may ask at most $4$ queries.

In each query, you choose a nonempty subset of the admissible points and you are told how many of the chosen points are inside or on the boundary of the invisible rectangle.

Interaction

To ask a query (of the kind described in the statement), you shall print two lines:

• In the first line print "? $k$" (without the quotes) where $k$ ($k\ge 1$) is the number of chosen points.
• In the second line print $2k$ integers $x_1,\, y_1,\, x_2,\, y_2,\, \dots,\, x_k,\, y_k$ ($1\le x_i,y_i\le 200$ for $i=1,2,\dots,k$) where $(x_1, y_1),\,(x_2, y_2),\,(x_3, y_3),\, \dots,\,(x_k, y_k)$ are the $k$ distinct admissible chosen points (the order of the points is not important).

After this, you should read an integer — the number of chosen points that are inside or on the boundary of the invisible rectangle.

When you have identified the perimeter $p$ of the invisible rectangle, you must print "! $p$" (without quotes) and terminate your program.

If you ask more than $4$ queries or if one of the queries is malformed, the interactor terminates immediately and your program receives verdict Wrong Answer.

The interactor may be adaptive (i.e., the hidden rectangle may not be chosen before the beginning of the interaction).

After printing a query do not forget to output end of line and flush the output. Otherwise, you will get Idleness limit exceeded. To do this, use:

• fflush(stdout) or cout.flush() in C++;
• System.out.flush() in Java;
• flush(output) in Pascal;
• stdout.flush() in Python;
• see documentation for other languages.

Hacks

To hack a solution, use the following format.

The input has only one line, containing the $4$ integers $x_0$, $y_0$, $x_1$, $y_1$ ($1\le x_0 \lt x_1\le 200$, $1\le y_0 \lt y_1 \le 200$) — $(x_0,y_0)$ is the bottom-left vertex of the hidden rectangle and $(x_1, y_1)$ is the top-right vertex of the hidden rectangle.

Note that for hacks the interaction won't be adaptive.

我们称平面上的一个点为可接受的，如果它的坐标均为不超过 $200$ 的正整数。

存在一个不可见的矩形，满足以下条件：

• 其四个顶点均为可接受的点；
• 其各边均与坐标轴平行；
• 其面积严格大于 $0$。

你的任务是猜出该矩形的周长。

为了进行猜测，你最多可提出 $4$ 次查询。

每次查询中，你选择一个非空的可接受点子集，系统将返回该子集中有多少个点位于该不可见矩形内部或其边界上。

交互方式

要提出一次查询（如题面所述），你需要输出两行：

• 第一行输出 "? $k$"（不含引号），其中 $k$（$k \ge 1$）为你所选点的数量；
• 第二行输出 $2k$ 个整数：$x_1,\, y_1,\, x_2,\, y_2,\, \dots,\, x_k,\, y_k$（对所有 $i = 1,2,\dots,k$，均有 $1 \le x_i, y_i \le 200$），表示所选的 $k$ 个互异的可接受点 $(x_1, y_1),\,(x_2, y_2),\,(x_3, y_3),\, \dots,\,(x_k, y_k)$（点的顺序无关紧要）。

随后，你需要读入一个整数——即所选点中位于该不可见矩形内部或其边界上的点的个数。

当你确定该不可见矩形的周长 $p$ 后，必须输出 "! $p$"（不含引号），然后终止程序。

如果你提出的查询次数超过 $4$ 次，或某次查询格式非法，则评测器将立即终止，并给出“答案错误”（Wrong Answer）判据。

评测器可能是自适应的（即隐藏矩形可能并非在交互开始前就已固定）。

每次输出查询后，请务必输出换行符并刷新输出缓冲区；否则你将收到“空闲超时”（Idleness limit exceeded）错误。为此，请使用以下方式：

• C++ 中：fflush(stdout) 或 cout.flush()；
• Java 中：System.out.flush()；
• Pascal 中：flush(output)；
• Python 中：stdout.flush()；
• 其他语言请参考相应文档。

Hack（构造测试数据）

要 hack 一个解法，请使用如下格式：

输入仅含一行，包含 $4$ 个整数 $x_0$, $y_0$, $x_1$, $y_1$（满足 $1 \le x_0 < x_1 \le 200$，$1 \le y_0 < y_1 \le 200$），其中 $(x_0,y_0)$ 是隐藏矩形的左下角顶点，$(x_1, y_1)$ 是其右上角顶点。

注意：对于 hack 测试，交互过程不是自适应的。

The following is an example of interaction for the first sample intended to show the format of the queries. $$ \begin{array}{l|l|l} \text{Query (contestant program)} & \text{Answer (interactor)} & \text{Explanation} \\ \hline \mathtt{?\ 4} & & \text{We choose the $4$ vertices of} \\ \mathtt{13\ 5\ 13\ 80\ 123\ 5\ 123\ 80} & \mathtt{4} &\text{the hidden rectangle.}\\ \hline \mathtt{?\ 5} & & \text{We choose $4$ points just outside the hidden}\\ \mathtt{100\ 4\ 100\ 81\ 12\ 40\ 124\ 40\ 50\ 50} & \mathtt{1}& \text{rectangle and also the point $(50,50)$.}\\ \hline \mathtt{?\ 2} & & \text{We choose the points $(1, 1)$} \\ \mathtt{200\ 200\ 1\ 1} & \mathtt{0} & \text{and $(200,200)$.}\\ \hline \mathtt{!\ 370} & & \text{This is the correct perimeter.} \end{array} $$

For the second sample, a possible interaction is the following. $$ \begin{array}{l|l|l} \text{Query (contestant program)} & \text{Answer (interactor)} & \text{Explanation} \\ \hline \mathtt{?\ 4} & & \text{We choose the points $(3, 2)$, $(4, 1)$,} \\ \mathtt{3\ 2\ 4\ 1\ 5\ 2\ 4\ 3} & 2 & \text{$(5, 2)$ and $(4, 3)$.} \\ \hline \mathtt{?\ 7} & & \text{We choose the points $(1, 4)$, $(2, 4)$,} \\ \mathtt{1\ 4\ 2\ 4\ 1\ 5\ 2\ 5\ 5\ 5\ 5\ 6\ 6\ 5} & 1 & \text{$(1, 5)$, $(2, 5)$, $(5, 5)$, $(5, 6)$ and $(6, 5)$.} \\ \hline \mathtt{!\ 8} & & \text{This is the correct perimeter.} \end{array} $$ The situation is shown in the following picture:

The green points are the ones belonging to the first query, while the orange points are the ones belonging to the second query. One can see that there are exactly two rectangles consistent with the interactor's answers:

• the rectangle of vertices $(2, 2)$ and $(4, 4)$, shown in red;
• the rectangle of vertices $(4, 2)$ and $(5, 5)$, shown in blue.

Since both of these rectangles have perimeter $8$, this is the final answer.

以下是第一个样例的交互过程示例，旨在展示查询格式。

$$\begin{array}{l|l|l} \text{查询（选手程序）} & \text{回答（交互器）} & \text{说明} \\ \hline \mathtt{?\ 4} & & \text{我们选取隐藏矩形的 } 4 \text{ 个顶点。} \\ \mathtt{13\ 5\ 13\ 80\ 123\ 5\ 123\ 80} & \mathtt{4} & \\ \hline \mathtt{?\ 5} & & \text{我们选取 } 4 \text{ 个恰好位于隐藏矩形外部的点，} \\ \mathtt{100\ 4\ 100\ 81\ 12\ 40\ 124\ 40\ 50\ 50} & \mathtt{1} & \text{以及点 } (50,50)\text{。} \\ \hline \mathtt{?\ 2} & & \text{我们选取点 } (1, 1) \\ \mathtt{200\ 200\ 1\ 1} & \mathtt{0} & \text{和 } (200,200)\text{。} \\ \hline \mathtt{!\ 370} & & \text{这是正确的周长。} \end{array}$$

对于第二个样例，一种可能的交互过程如下：

$$\begin{array}{l|l|l} \text{查询（选手程序）} & \text{回答（交互器）} & \text{说明} \\ \hline \mathtt{?\ 4} & & \text{我们选取点 } (3, 2),\ (4, 1), \\ \mathtt{3\ 2\ 4\ 1\ 5\ 2\ 4\ 3} & 2 & (5, 2) \text{ 和 } (4, 3)\text{。} \\ \hline \mathtt{?\ 7} & & \text{我们选取点 } (1, 4),\ (2, 4), \\ \mathtt{1\ 4\ 2\ 4\ 1\ 5\ 2\ 5\ 5\ 5\ 5\ 6\ 6\ 5} & 1 & (1, 5),\ (2, 5),\ (5, 5),\ (5, 6) \text{ 和 } (6, 5)\text{。} \\ \hline \mathtt{!\ 8} & & \text{这是正确的周长。} \end{array}$$

该情形如以下图片所示：

绿色点属于第一次查询，橙色点属于第二次查询。可以看出，恰好存在两个与交互器回答一致的矩形：

• 以 $(2, 2)$ 和 $(4, 4)$ 为对角顶点的矩形（红色）；
• 以 $(4, 2)$ 和 $(5, 5)$ 为对角顶点的矩形（蓝色）。

由于这两个矩形的周长均为 $8$，因此最终答案为 $8$。