A. 物体识别

时间限制：每个测试点 $2$ 秒
内存限制： $256$ MB

本题为交互题。

题目描述

你已知一个数组 $x_1, x_2, \dots, x_n$ ，其中每个 $x_i$ 是 $1$ 到 $n$ 之间的整数。
评测系统拥有一个固定但隐藏的数组 $y_1, y_2, \dots, y_n$ ，每个 $y_i$ 也是 $1$ 到 $n$ 之间的整数，但你不清楚它的内容。
此外，保证对于所有 $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 \le i, j \le n$ ， $i \neq j$ ），然后你会收到一个数字作为回答：

如果评测系统选择的是物体 A，你会收到从顶点 $i$ 到顶点 $j$ 的最短路径长度（边数）；如果不存在路径，则返回 $0$ 。
如果评测系统选择的是物体 B，你会收到点 $i$ 和点 $j$ 之间的曼哈顿距离，即 $|x_i - x_j| + |y_i - y_j|$ 。

你最多可以进行 $2$ 次查询，以确定评测系统选择的是物体 A 还是物体 B。

输入格式

每个测试点包含多个测试用例。
第一行输入一个整数 $t$ （ $1 \le t \le 1000$ ），表示测试用例的数量。

每个测试用例开始时，首先读取 $n$ （ $3 \le n \le 2 \times 10^5$ ）——数组的长度。
接下来读取 $n$ 个整数 $x_1, x_2, \dots, x_n$ （ $1 \le x_i \le n$ ）。

保证所有测试用例的 $n$ 之和不超过 $2 \times 10^5$ 。
数组 $y_1, y_2, \dots, y_n$ 在每个测试用例中是固定的，并且交互器是非自适应的（即不会根据你的查询改变隐藏数据）。

交互协议

发起查询：输出 ? i j（不含引号， $1 \le i, j \le n$ ， $i \neq j$ ），然后读取一个整数作为回答。
给出答案：输出 ! A 或 ! B（表示你认为隐藏的是物体 A 或物体 B）。
注意：输出答案不计入那 $2$ 次查询。

每次输出后必须刷新输出缓冲区（例如 C++ 中使用 fflush(stdout) 或 cout.flush()，Python 中使用 sys.stdout.flush()）。
如果读取到 $-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。

黑客（Hack）格式

第一行一个整数 $t$ （ $1 \le t \le 1000$ ），表示测试用例数量。
每个测试用例：

第一行： $n$ （ $3 \le n \le 2 \times 10^5$ ）
第二行： $n$ 个整数 $x_1, x_2, \dots, x_n$ （ $1 \le x_i \le n$ ）
第三行： $n$ 个整数 $y_1, y_2, \dots, y_n$ （ $1 \le y_i \le n$ ）
保证 $x_i \neq y_i$ 且所有 $(x_i, y_i)$ 互不相同
第四行：一个字符 A 或 B，表示你想要隐藏的物体

所有测试用例的 $n$ 之和不超过 $2 \times 10^5$ 。

#CF2066A. 物体识别

物体识别