310786: CF1887E. Good Colorings

E. Good Coloringstime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

Alice suggested Bob to play a game. Bob didn't like this idea, but he couldn't refuse Alice, so he asked you to write a program that would play instead of him.

The game starts with Alice taking out a grid sheet of size $n \times n$, the cells of which are initially not colored. After that she colors some $2n$ cells with colors $1,2,\ldots, 2n$, respectively, and informs Bob about these cells.

In one move, Bob can point to a cell that has not been colored yet and ask Alice to color that cell. Alice colors that cell with one of the $2n$ colors of her choice, informing Bob of the chosen color. Bob can make no more than $10$ moves, after which he needs to find a good set of four cells.

A set of four cells is considered good if the following conditions are met:

• All the cells in the set are colored;
• No two cells in the set are colored with the same color;
• The centers of the cells form a rectangle with sides parallel to the grid lines.

Input

Each test consists of multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 200$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($3 \le n \le 1000$) — the size of the grid.

The $i$-th of the following $2n$ lines contains two integers $x_i$ and $y_i$ ($1 \le x_i, y_i \le n$) — the coordinates of the cell colored with the $i$-th color.

It is guaranteed that all coordinates $(x_i, y_i)$ are pairwise distinct for the same test case.

After reading the input data for each test case, continue the interaction as described below.

Interaction

You can make no more than $10$ moves. To make a move, output "? $x$ $y$" ($1 \leq x,y \leq n$). In response to this, the jury's program will output a single integer from $1$ to $2n$ — the color of cell $(x,y)$.

After all moves (it is not necessary to make all $10$ moves and it is not necessary to make at least one move), output a string in the format "! $x_1$ $x_2$ $y_1$ $y_2$" ($1 \leq x_1, x_2, y_1, y_2 \leq n, x_1 \ne x_2, y_1 \ne y_2$). If cells $(x_1, y_1)$, $(x_1, y_2)$, $(x_2, y_1)$, $(x_2, y_2)$ are colored with different colors, the jury's program will output "OK". After that, proceed to the next test case or terminate the program if there are no more test cases left.

Otherwise, if any of the specified cells are colored with the same color or one of the cells is not colored yet, the jury's program will output "ERROR". In this case, your program should immediately terminate its execution to receive the Wrong Answer verdict. Otherwise, you may receive an arbitrary verdict.

After each move or answer, do not forget to output the end of line and flush the output. Otherwise, you will get the Idleness limit exceeded verdict.

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.

Note that the interactor is adaptive, meaning that the color Alice will use to color the cells during Bob's moves is not fixed in advance.

Hacks

You cannot use hacks in this problem.

ExampleInput

2
3
1 2
1 3
2 1
2 3
3 1
3 2

1

OK
3
1 1
1 2
1 3
2 1
2 2
2 3

OK

Output

? 1 1

! 1 2 1 3








! 1 2 1 2

Note

In the first test case:

In the second test case, cells with coordinates $(1, 1), (1, 2), (2, 1), (2, 2)$ are initially colored by Alice in different colors.

题目大意：
爱丽丝建议鲍勃玩一个游戏。鲍勃不喜欢这个主意，但他无法拒绝爱丽丝，所以他要求你写一个程序来代替他玩。

游戏从爱丽丝拿出一个尺寸为 \( n \times n \) 的网格纸开始，这些单元格最初未着色。之后她用颜色 \( 1,2,\ldots, 2n \) 分别给 \( 2n \) 个单元格着色，并通知鲍勃这些单元格。

鲍勃每移动一次，可以指出一个尚未着色的单元格并要求爱丽丝着色。爱丽丝用她选择的 \( 2n \) 种颜色中的一种着色该单元格，并通知鲍勃所选颜色。鲍勃最多可以进行 \( 10 \) 次移动，之后他需要找到一个“好”的四单元格集合。

如果四单元格集合满足以下条件，则被认为是好的：
- 集合中的所有单元格都被着色；
- 集合中没有两个单元格着色相同；
- 单元格的中心形成一个与网格线平行的矩形。

输入输出数据格式：
每个测试用例包含多个测试。第一行包含一个整数 \( t \)（\( 1 \le t \le 200 \)）——测试用例的数量。接下来是测试用例的描述。

每个测试用例的第一行包含一个整数 \( n \)（\( 3 \le n \le 1000 \)）——网格的大小。

接下来的 \( 2n \) 行中的第 \( i \) 行包含两个整数 \( x_i \) 和 \( y_i \)（\( 1 \le x_i, y_i \le n \)）——用第 \( i \) 种颜色着色的单元格的坐标。

保证对于同一个测试用例，所有坐标 \( (x_i, y_i) \) 都是不同的。

在每个测试用例读取输入数据后，继续按以下描述进行交互。

你最多可以进行 \( 10 \) 次移动。为了进行一次移动，输出 "<问号> x y"（\( 1 \leq x,y \leq n \)）。作为响应，评审程序的输出将是一个从 \( 1 \) 到 \( 2n \) 的整数——单元格 \( (x,y) \) 的颜色。

在所有移动之后（不需要进行所有 \( 10 \) 次移动，也不需要至少进行一次移动），输出一个格式为 "<叹号> \( x_1 \) \( x_2 \) \( y_1 \) \( y_2 \)" 的字符串（\( 1 \leq x_1, x_2, y_1, y_2 \leq n, x_1 \ne x_2, y_1 \ne y_2 \)）。如果单元格 \( (x_1, y_1) \), \( (x_1, y_2) \), \( (x_2, y_1) \), \( (x_2, y_2) \) 被着以不同的颜色，评审程序将输出 "OK"。之后，继续下一个测试用例或如果不再有测试用例，则终止程序。

否则，如果指定的任一单元格被着以相同的颜色或其中一个单元格尚未着色，评审程序将输出 "ERROR"。在这种情况下，你的程序应该立即终止其执行以获得“错误答案”的裁决。否则，你可能会收到任意裁决。

在每次移动或回答后，不要忘记输出行尾并刷新输出。否则，你将得到“空闲限制超出”的裁决。

为此，请使用：
- 在 C++ 中：`fflush(stdout)` 或 `cout.flush()`;
- 在 Java 中：`System.out.flush()`;
- 在 Pascal 中：`flush(output)`;
- 在 Python 中：`stdout.flush()`;
- 参阅其他语言的文档。

注意，交互器是自适应的，这意味着爱丽丝在鲍勃的移动过程中用来着色单元格的颜色并不是提前固定的。

你不能在这个问题中使用破解。

示例输入输出格式：
输入：
```
2
3
1 2
1 3
2 1
2 3
3 1
3 2

1

OK
3
1 1
1 2
1 3
2 1
2 2
2 3

OK
```
输出：
```
? 1 1

! 1 2 1 3

! 1 2 1 2
```

注意：
在第一个测试用例中，单元格坐标为 \( (1, 2) \), \( (1, 3) \), \( (2, 1) \), \( (3, 2) \) 的单元格最初被爱丽丝用不同的颜色着色。

在第二个测试用例中，单元格坐标为 \( (1, 1)题目大意： 爱丽丝建议鲍勃玩一个游戏。鲍勃不喜欢这个主意，但他无法拒绝爱丽丝，所以他要求你写一个程序来代替他玩。 游戏从爱丽丝拿出一个尺寸为 \( n \times n \) 的网格纸开始，这些单元格最初未着色。之后她用颜色 \( 1,2,\ldots, 2n \) 分别给 \( 2n \) 个单元格着色，并通知鲍勃这些单元格。 鲍勃每移动一次，可以指出一个尚未着色的单元格并要求爱丽丝着色。爱丽丝用她选择的 \( 2n \) 种颜色中的一种着色该单元格，并通知鲍勃所选颜色。鲍勃最多可以进行 \( 10 \) 次移动，之后他需要找到一个“好”的四单元格集合。 如果四单元格集合满足以下条件，则被认为是好的： - 集合中的所有单元格都被着色； - 集合中没有两个单元格着色相同； - 单元格的中心形成一个与网格线平行的矩形。 输入输出数据格式： 每个测试用例包含多个测试。第一行包含一个整数 \( t \)（\( 1 \le t \le 200 \)）——测试用例的数量。接下来是测试用例的描述。 每个测试用例的第一行包含一个整数 \( n \)（\( 3 \le n \le 1000 \)）——网格的大小。 接下来的 \( 2n \) 行中的第 \( i \) 行包含两个整数 \( x_i \) 和 \( y_i \)（\( 1 \le x_i, y_i \le n \)）——用第 \( i \) 种颜色着色的单元格的坐标。 保证对于同一个测试用例，所有坐标 \( (x_i, y_i) \) 都是不同的。 在每个测试用例读取输入数据后，继续按以下描述进行交互。 你最多可以进行 \( 10 \) 次移动。为了进行一次移动，输出 "<问号> x y"（\( 1 \leq x,y \leq n \)）。作为响应，评审程序的输出将是一个从 \( 1 \) 到 \( 2n \) 的整数——单元格 \( (x,y) \) 的颜色。 在所有移动之后（不需要进行所有 \( 10 \) 次移动，也不需要至少进行一次移动），输出一个格式为 "<叹号> \( x_1 \) \( x_2 \) \( y_1 \) \( y_2 \)" 的字符串（\( 1 \leq x_1, x_2, y_1, y_2 \leq n, x_1 \ne x_2, y_1 \ne y_2 \)）。如果单元格 \( (x_1, y_1) \), \( (x_1, y_2) \), \( (x_2, y_1) \), \( (x_2, y_2) \) 被着以不同的颜色，评审程序将输出 "OK"。之后，继续下一个测试用例或如果不再有测试用例，则终止程序。 否则，如果指定的任一单元格被着以相同的颜色或其中一个单元格尚未着色，评审程序将输出 "ERROR"。在这种情况下，你的程序应该立即终止其执行以获得“错误答案”的裁决。否则，你可能会收到任意裁决。 在每次移动或回答后，不要忘记输出行尾并刷新输出。否则，你将得到“空闲限制超出”的裁决。 为此，请使用： - 在 C++ 中：`fflush(stdout)` 或 `cout.flush()`; - 在 Java 中：`System.out.flush()`; - 在 Pascal 中：`flush(output)`; - 在 Python 中：`stdout.flush()`; - 参阅其他语言的文档。 注意，交互器是自适应的，这意味着爱丽丝在鲍勃的移动过程中用来着色单元格的颜色并不是提前固定的。 你不能在这个问题中使用破解。 示例输入输出格式： 输入： ``` 2 3 1 2 1 3 2 1 2 3 3 1 3 2 1 OK 3 1 1 1 2 1 3 2 1 2 2 2 3 OK ``` 输出： ``` ? 1 1 ! 1 2 1 3 ! 1 2 1 2 ``` 注意： 在第一个测试用例中，单元格坐标为 \( (1, 2) \), \( (1, 3) \), \( (2, 1) \), \( (3, 2) \) 的单元格最初被爱丽丝用不同的颜色着色。 在第二个测试用例中，单元格坐标为 \( (1, 1)