D. 对象识别
每个测试的时间限制：2 秒
每个测试的内存限制：256 兆字节

这是一个交互式问题。

你有一个数组 $x_1, \dots, x_n$，其中的数字是从 $1$ 到 $n$ 的整数。
评测系统有一个固定但隐藏的数组 $y_1, \dots, y_n$，其中的数字也是从 $1$ 到 $n$ 的整数，但数组 $y$ 对你来说是不可知的。
此外，已知对于所有 $i$ 都有 $x_i \ne 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 \le i, j \le n, i \ne 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 \le n \le 2 \cdot 10^5$），表示数组 $x$ 和 $y$ 的长度。
• 接下来读取 $n$ 个整数：$x_1, x_2, \dots, x_n$（$1 \le x_i \le n$）。

保证：

• 所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。
• 数组 $y$ 在测试用例开始时就固定了（交互器是非自适应的）。
• 对于所有 $i$，有 $x_i \ne y_i$，且所有 $(x_i, y_i)$ 对互不相同。

---

交互方式

• 要发起一次查询，输出 ? i j（不带引号，$1 \le i, j \le n, i \ne j$），然后读取回复。
• 要给出答案，输出 ! A（如果是对象 A）或 ! B（如果是对象 B）。输出答案不计入两次查询限制。

每次输出后要刷新输出缓冲区（flush），否则会得到 Idleness limit exceeded。
如果交互过程中读到 $-1$，说明查询非法或出现了其他错误，此时你的程序必须立即退出，否则可能得到任意评测结果。如果查询正确，返回值不会是 $-1$。

---

Hacks 模式（用于本地测试）

第一行：$t$
每个测试用例：

• 第一行：$n$
• 第二行：$n$ 个整数 $x_1, \dots, x_n$
• 第三行：$n$ 个整数 $y_1, \dots, y_n$（满足 $x_i \ne y_i$ 且 $(x_i, y_i)$ 互不相同）
• 第四行：一个字符 A 或 B，表示你要隐藏的对象

所有 $n$ 之和不超过 $2 \cdot 10^5$。

---

样例

输入：

2
3
2 2 3

1

0

5
5 1 4 2 3

4

4

输出：

? 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（点）。