P15143 [SWERC 2025] Isaac's Queries

你已到达热门 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()`； - 其他语言请参阅相关文档。

See Interaction

#### 样例解释 在样例中，隐藏数组为 $[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 完成