Description

这是一道交互题。

有一个无限大的正方形网格对你隐藏。每个单元格由一对整数 $(x, y)$ 标识，并且以 $50\%$ 的概率随机染成黑色或白色，各单元格的颜色相互独立。

如果两个单元格共享一条边或一个角，则认为它们是 相邻的。因此，每个单元格 $(x, y)$ 有 $8$ 个相邻单元格：$(x-1, y-1)$、$(x-1, y)$、$(x-1, y+1)$、$(x, y-1)$、$(x, y+1)$、$(x+1, y-1)$、$(x+1, y)$ 和 $(x+1, y+1)$。

如果对于集合 $S$ 中的任意两个单元格，存在一条仅使用 $S$ 中单元格的路径连接它们，且路径中连续的单元格是相邻的，则称单元格集合 $S$ 是 八连通的。

在一次查询中，你可以了解网格上任意单元格的颜色。你的任务是找到一个包含 $n$ 个单元格的八连通集合，且该集合中的所有单元格颜色相同。

你需要解决 $t$ 个测试用例。在每个测试用例中，网格的染色是随机的，且与其他测试用例相互独立。

在所有测试用例中，你最多可以进行 $30,000$ 次查询。

Input Format

第一行包含两个整数 $t$ 和 $n$，分别表示测试用例的数量和所需的八连通集合的大小（$1 \le t \le 50$；$2 \le n \le 300$）。

交互协议

在每个测试用例中，你可以进行零次或多次查询以了解网格单元格的颜色。

要进行查询，请输出一行：

• ? $x$ $y$

其中 $(x, y)$ 是请求单元格的坐标（$-10^9 \le x, y \le 10^9$）。之后，读取一行包含一个字母：如果单元格 $(x, y)$ 是黑色则为 B，如果是白色则为 W。

当你准备好呈现一个包含 $n$ 个同色单元格的八连通集合时，输出一行：

• ! $c$ $x_1$ $y_1$ $x_2$ $y_2$ $\ldots$ $x_n$ $y_n$

其中 $c$ 是表示集合中单元格颜色的字母（黑色为 B，白色为 W），而 $(x_1, y_1), (x_2, y_2), \ldots, (x_n, y_n)$ 是集合中的 $n$ 个不同单元格（$-10^9 \le x_i, y_i \le 10^9$）。交互器不会对此行作出任何响应。

输出集合后，继续处理下一个测试用例，或者如果这是最后一个测试用例则终止程序。

在所有测试用例中（不包括输出集合的行），你最多可以进行 $30,000$ 次查询。如果你超过此限制，交互器将输出 $0$ 而不是通常的响应，你的程序应立即终止以保证获得错误答案的判定。

交互器不是自适应的：测试中使用的所有随机网格都是预先生成的，并且在所有提交中保持不变。

2 5

W

W

B

B

B

W

B

B

B


B

W

W

B

B

W

W

W

B

? 1 1

? 1 2

? 1 3

? 2 1

? 2 2

? 2 3

? 3 1

? 3 2

? 3 3

! B 2 2 1 3 3 3 2 1 3 2
? 1 1

? 1 2

? 1 3

? 2 1

? 2 2

? 2 3

? 3 1

? 3 2

? 3 3

! W 1 2 3 2 1 3 2 3 3 1

Hint

在示例中，为了清晰起见，查询和响应之间用空行分隔。在你的程序与交互器的实际交互中，不会有空行。

你的解决方案将在最多 $60$ 个测试文件上进行评估。

翻译由 DeepSeek V3 完成