CF1887E.Good Colorings

Alice 建议 Bob 玩一个游戏。Bob 并不喜欢这个主意，但他无法拒绝 Alice，于是他请求你写一个程序来代替他玩这个游戏。

游戏开始时，Alice 拿出一张 $n \times n$ 的方格纸，所有格子最初都是未染色的。随后，她用颜色 $1,2,\ldots,2n$ 分别染色了 $2n$ 个格子，并将这些格子的位置信息告知 Bob。

在每一步中，Bob 可以指向一个尚未染色的格子，并请求 Alice 给该格子染色。Alice 会用她选择的 $2n$ 种颜色中的一种为该格子染色，并告知 Bob 所选颜色。Bob 最多只能进行 $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"。此时你的程序应立即终止，否则会被判为 Wrong Answer。否则，你可能会收到任意评测结果。

每次操作或输出答案后，别忘了输出换行并刷新输出缓冲区，否则会被判为 Idleness limit exceeded。

为此，请使用：

• C++：fflush(stdout) 或 cout.flush()
• Java：System.out.flush()
• Pascal：flush(output)
• Python：stdout.flush()
• 其它语言请查阅相关文档。

注意，交互器是自适应的，也就是说 Alice 在 Bob 操作时为格子染色的颜色并不是预先确定的。

Hack

本题不支持 Hack。

在第一个测试用例中：

在第二个测试用例中，坐标为 $(1, 1), (1, 2), (2, 1), (2, 2)$ 的格子最初就被 Alice 染上了不同的颜色。

由 ChatGPT 4.1 翻译