说明

你已到达热门 roguelike 游戏 Isaac’s Keybindings 的最后一关。你遇到的不是 Boss，而是一位商店老板，他持有一个隐藏的整数数组 $a_1, a_2, \ldots, a_n$，其中对每个 $i \in [1, n]$ 有 $0 \le a_i < 2^{30}$。

保证该数组是随机生成的，即除样例外，在所有测试中每个 $i \in [1, n]$ 的 $a_i$ 是 $[0, 2^{30})$ 上的均匀随机整数。

定义 $f(u, v) = a_u \oplus a_{u+1} \oplus \ldots \oplus a_v$，其中 $\oplus$ 表示按位异或。

你可以提出以下格式的询问：? u v，其中 $1 \le u \le v \le n$。

询问的答案是：

• 若 $f(u, v) = 0$，则为 $-1$；
• 否则为 $\lfloor \log_2(f(u, v)) \rfloor$。

每次询问的成本为 $\frac{1}{v - u + 1}$ 机器人币。你初始拥有 $35$ 机器人币，如果余额变为负数则失败。注意，你的机器人币余额在任何时刻都不必是整数。

在不失败的前提下，找出所有可能的 $\frac{n(n+1)}{2}$ 次询问的答案。

输入格式

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 30$）。接下来是测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 100$）—— 数组 $a_1, a_2, \ldots, a_n$ 的长度。保证除样例外，在所有测试中该数组是随机生成的。

本题共有恰好 $50$ 个测试（包括样例）。样例的 $t = 1$ 且 $n = 3$，所有其他测试的 $t = 30$ 且 $n = 100$。

交互说明

对于每个测试用例，首先读取一个整数 $n$。如果你读取到的整数是 $-2$，表示前一个测试用例的答案错误，你应当立即退出。

要提出一个询问，请打印一行格式为 ? u v，其中 $1 \le u \le v \le n$。

作为询问的响应，如果你提出了无效的询问（即格式无效，或者会导致机器人币余额为负），你将收到 $-2$。此时你应当立即退出。否则，你将收到该询问的答案。

当你确定了所有 $\frac{n(n+1)}{2}$ 次询问的答案后，按以下格式输出。

打印 $n + 1$ 行。第一行必须包含单个字符 !。接下来的 $n$ 行中，第 $i$ 行必须包含 $n - i + 1$ 个整数：分别对应询问 ? i i、? i i+1、……、? i n 的答案。

打印询问后，请不要忘记输出换行并刷新输出缓冲区。为此，请使用：

• C++ 中的 fflush(stdout) 或 cout.flush()；
• Java 中的 System.out.flush()；
• Python 中的 stdout.flush()；
• 其他语言请参阅相关文档。

1
3
2 4 6

? 1 2

? 1 3

? 2 3

!
1 2 -1
2 1
2

提示

样例解释

在样例中，隐藏数组为 $[a_1, a_2, a_3] = [2, 4, 6]$。

• 首先，你询问 ? 1 2。由于 $f(1,2) = a_1 \oplus a_2 = 6$，答案为 $\lfloor \log_2(6) \rfloor = 2$。
• 然后，你询问 ? 1 3。由于 $f(1,3) = a_1 \oplus a_2 \oplus a_3 = 0$，答案为 $-1$。
• 最后，你询问 ? 2 3。由于 $f(2,3) = a_2 \oplus a_3 = 2$，答案为 $\lfloor \log_2(2) \rfloor = 1$。

现在，即使不知道隐藏数组，你也可以声明所有可能的 $6$ 次询问的答案。例如，你声明 ? 1 1 的答案为 $1$。

你花费了 $\frac{1}{2} + \frac{1}{3} + \frac{1}{2} = \frac{4}{3}$ 机器人币，这小于允许的 $35$ 机器人币。

翻译由 DeepSeek 完成