您已达到流行 Roguelike 游戏“艾萨克的按键绑定”的最终级别。你遇到的不是老板,而是一个店主,他持有一个隐藏的整数数组 $$$a_1, a_2, \ldots, a_n$$$,其中 $$$0 \leq a_i \lt 2^{30}$$$ 对于 $$$[1, n]$$$ 中的每个 $$$i$$$。
保证 数组是随机生成的,即,在除示例之外的所有测试中,每个 $$$a_i$$$ ($$$1 \leq i \leq n$$$) 是 $$$[0, 2^{30})$$$ 中独立均匀随机生成的整数。
设 $$$f(u, v) = a_u \oplus a_{u+1} \oplus \ldots \oplus a_v$$$,其中 $$$\oplus$$$ 是按位 $$$\texttt{XOR}$$$。
您可以提出以下形式的查询:$$$\texttt{? u v}$$$,其中 $$$1 \leq u \leq v \leq n$$$。
查询的答案是:
- $$$-1$$$,如果 $$$f(u, v) = 0$$$;
- $$$\lfloor \log_2(f(u, v)) \rfloor$$$ 否则。
每个查询的成本为 $$$\frac{1}{v-u+1}$$$ 机器人币。在每次测试中,您总共会获得 $$$300$$$ 机器人币来通过最多 $$$30$$$ 测试用例(也就是说,您平均可以在单个测试用例中花费 $$$10$$$ 机器人币)。如果您的余额变为负数,您就会输。请注意,您的 robocoin 余额在任何时候都不需要是整数。
找到所有可能的 $$$\frac{n(n+1)}{2}$$$ 查询的答案而不丢失。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 30$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$($$$n = 3$$$ 或 $$$n = 100$$$)——数组 $$$a_1, a_2, \ldots, a_n$$$ 的长度。保证在除示例之外的所有测试中数组都是随机生成的。
这个问题总共有 $$$50$$$ 测试(包括示例)。该示例具有 $$$t = 1$$$ 和 $$$n = 3$$$,所有其他测试具有 $$$t = 30$$$ 和 $$$n = 100$$$。
此问题不允许进行黑客攻击。
互动
对于每个测试用例,首先读取单个整数 $$$n$$$。如果你读到的整数是$$$-2$$$,则说明前面的测试用例的答案是错误的,你应该立即退出。
要提出查询,请以 $$$\texttt{? 格式打印一行u v}$$$ 与 $$$1 \leq u \leq v \leq n$$$。
作为对查询的响应,如果您进行了无效查询(即格式无效,或者您将达到负数的 robocoins),您将收到 $$$-2$$$。在这种情况下,您应该立即退出。否则,您将收到查询的答案。
当您确定所有 $$$\frac{n(n+1)}{2}$$$ 查询的答案时,请按以下格式打印它们。
打印 $$$n+1$$$ 行。第一行必须包含单个字符 $$$\texttt{!}$$$。接下来的 $$$n$$$ 行的第 $$$i$$$ 必须包含 $$$n-i+1$$$ 整数:查询的答案 $$$\texttt{?我我}, \, \texttt{? i i+1}, \,\ldots, \, \texttt{?我分别是}$$$。
打印查询后,不要忘记输出行尾并刷新输出。否则,您将得到$$$\texttt{超出空闲限制}$$$。为此,请使用:
- $$$\texttt{fflush(stdout)}$$$ 或 $$$\texttt{cout.flush()}$$$ 在 C++ 中;
- $$$\texttt{System.out.flush()}$$$ 在 Java 中;
- $$$\texttt{stdout.flush()}$$$ 在 Python 中;
- 请参阅其他语言的文档。
示例
输入复制
1 3 2 -1 1
输出复制
? 1 2 ? 1 3 ? 2 3 ! 1 2 -1 2 1 2
注意
在示例中,隐藏数组为 $$$[a_1, a_2, a_3] = [2, 4, 6]$$$。
- 首先,你问$$$\texttt{? 1 2}$$$。由于 $$$f(1, 2) = a_1 \oplus a_2 = 6$$$,所以答案是 $$$\lfloor \log_2(6) \rfloor = 2$$$。
- 然后,你问 $$$\texttt{? 1 3}$$$。由于 $$$f(1, 3) = a_1 \oplus a_2 \oplus a_3 = 0$$$,所以答案是 $$$-1$$$。
- 然后,你问 $$$\texttt{? 2 3}$$$。由于 $$$f(2, 3) = a_2 \oplus a_3 = 2$$$,所以答案是 $$$\lfloor \log_2(2) \rfloor = 1$$$。
现在,即使不知道隐藏数组,您也可以获取所有可能的 $$$6$$$ 查询的答案。例如,您声称 $$$\texttt{? 的答案是1 1}$$$ 是 $$$1$$$。
您已花费 $$$1/2 + 1/3 + 1/2 = 4/3$$$ 机器人币,低于允许的 $$$300$$$ 机器人币。