这是一个交互式问题。

一个无限大的方格网格对你隐藏。每个格子由一对整数 $(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$ 次查询。

输入格式

第一行包含两个整数 $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'；如果格子 $(x, y)$ 是白色，则为 'W'。

一旦你准备好给出一个由相同颜色的 $n$ 个格子组成的八连通集合，请输出一行：

• ! c x1 y1 x2 y2 ... xn yn

其中 $c$ 是表示集合中格子颜色的字母（'B' 表示黑色，'W' 表示白色），且 $(x_1, y_1), (x_2, y_2), \dots, (x_n, y_n)$ 是集合中的 $n$ 个互不相同的格子（$-10^9 \le x_i, y_i \le 10^9$）。交互器不会对这一行做出任何回应。

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

在所有测试用例中，你总共最多允许进行 $30\,000$ 次查询（不包括输出集合的行）。如果超过此限制，交互器将输出 0 而不是其通常的响应，此时你的程序应立即终止以确保获得“Wrong Answer”评级。

交互器是非适应性的：测试中使用的所有随机网格均已预先生成，并且在所有提交中保持一致。

样例

输入格式 1

2 5
W
W
B
B
B
W
B
B
B
B
W
W
B
B
W
W
W
B

输出格式 1

? 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

说明

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

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