这是一个交互问题。
给定一个数组 $$$x_1, \ldots, x_n$$$,其中的整数从 $$$1$$$ 到 $$$n$$$。陪审团还有一个固定但隐藏的数组 $$$y_1, \ldots, y_n$$$,其整数从 $$$1$$$ 到 $$$n$$$。您不知道数组 $$$y$$$ 的元素。此外,已知对于所有 $$$i$$$,$$$x_i \neq y_i$$$ 以及所有对 $$$(x_i, y_i)$$$ 都是不同的。
陪审团秘密想到了两个物体之一,你需要确定它是哪一个:
- 对象 A:一个有向图,其中 $$$n$$$ 顶点编号从 $$$1$$$ 到 $$$n$$$,并且 $$$n$$$ 边的形式为 $$$x_i \to y_i$$$。
- 对象 B:坐标平面上的 $$$n$$$ 点。第 $$$i$$$ 点的坐标为 $$$(x_i, y_i)$$$。
要猜测陪审团想到了哪个对象,您可以进行查询。在一个查询中,您必须指定两个数字 $$$i, j$$$ $$$(1 \leq i, j \leq n, i \neq j)$$$。作为回应,您会收到一个号码:
- 如果陪审团想到了对象 A,您将收到图中从顶点 $$$i$$$ 到顶点 $$$j$$$ 的最短路径(以边为单位)的长度,如果没有路径,则为 $$$0$$$。
- 如果陪审团想到了对象 B,您将收到点 $$$i$$$ 和 $$$j$$$ 之间的曼哈顿距离,即 $$$|x_i -x_j| + |y_i - y_j|$$$。
您有 $$$2$$$ 查询来确定陪审团想到了哪些对象。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 1000$$$)。测试用例的描述如下。
互动
交互从读取 $$$n$$$ ($$$3 \leq n \leq 2 \cdot 10^5$$$) 开始——每个测试用例开始时数组 $$$x$$$ 和 $$$y$$$ 的长度。
接下来,读取 $$$n$$$ 整数:$$$x_1, x_2, \ldots, x_n$$$ ($$$1 \leq x_i \leq n$$$) — 数组 $$$x$$$ 的元素。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
每个测试用例的数组 $$$y_1, y_2, \ldots, y_n$$$ 是固定的。换句话说,交互器不具有适应性。
保证 $$$x_i \neq y_i$$$ 对于所有 $$$1 \leq i \leq n$$$ 来说,并且所有对 $$$(x_i, y_i)$$$ 都是不同的。
要进行查询,请输出“? $$$i$$$ $$$j$$$”(不带引号,$$$1 \le i, j \le n, i \neq j$$$)。然后您必须读取查询的响应,它是一个非负整数。
要给出答案,如果对象 A 被隐藏,则输出“! A”;如果对象 B 被隐藏,则输出“! B”(不带引号)。请注意,打印答案不算作 $$$2$$$ 查询之一。
打印每个查询后,不要忘记输出行尾并刷新$$$^{\text{*}}$$$ 输出。否则,您将得到超出空闲限制的判决。如果在任何交互步骤中您读取 $$$-1$$$ 而不是有效数据,则您的解决方案必须立即退出。这意味着您的解决方案将由于无效查询或任何其他错误而收到错误答案。未能退出可能会导致任意判决,因为您的解决方案将继续从关闭的流中读取。 请注意,如果查询正确,响应将永远不会是 $$$-1$$$。
黑客
第一行必须包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 测试用例的数量。
每个测试用例的第一行必须包含一个整数 $$$n$$$ ($$$3 \le n \le 2 \cdot 10^5$$$) - 隐藏数组的长度。
每个测试用例的第二行必须包含 $$$n$$$ 整数 — $$$x_1, x_2, \ldots, x_n$$$ ($$$1 \le x_i \le n$$$)。
每个测试用例的第三行必须包含 $$$n$$$ 整数 — $$$y_1, y_2, \ldots, y_n$$$ ($$$1 \le y_i \le n$$$)。
必须确保所有 $$$1 \le i \le n$$$ 的 $$$x_i \neq y_i$$$ ,并且所有对 $$$(x_i, y_i)$$$ 必须不同。
第四行必须包含一个字符:A 或 B,指示要隐藏哪个对象。
所有测试用例的 $$$n$$$ 总和不得超过 $$$2 \cdot 10^5$$$。
示例
输入 #1
2 3 2 2 3 1 0 5 5 1 4 2 3 4 4
输出 #1
? 2 3 ? 1 2 ! A ? 1 5 ? 5 1 ! B
注意
在第一个测试用例中,$$$x = [2,2,3]$$$,$$$y = [1,3,1]$$$ 并且猜测对象 A。
在第二个测试用例中,$$$x = [5,1,4,2,3]$$$,$$$y = [3,3,2,4,1]$$$,并且猜测对象 B。