P17272 [eJOI 2026] XORting

*这是一道交互题。* Iliyan 对 Jonas 开了一个恶作剧：他藏起了整数 $0$ 到 $N-1$ 的一个排列 $p_0,p_1,\ldots,p_{N-1}$。Jonas 很想恢复这个排列，而你答应帮助他。 Iliyan 不会直接公布排列，但同意回答如下问题：你可以选择满足 $0\le i,j

输入格式： - 第 $1$ 行：两个整数 $T$ 和 $Q_{\mathrm{type}}$，其中 $Q_{\mathrm{type}}$ 为 $1$ 或 $2$； - 接下来的 $2T$ 行描述各个测试： - 第 $2i$ 行：一个整数 $N_i$； - 第 $2i+1$ 行：$N_i$ 个整数 $p_0,p_1,\ldots,p_{N_i-1}$。 若 $Q_{\mathrm{type}}=1$，则 $Q_i=N_i$；若 $Q_{\mathrm{type}}=2$，则 $Q_i=N_i^2$。

输出格式： - 第 $i$ 行：程序在第 $i$ 个测试中返回的排列。

### 样例 考虑如下交互，其中 `solve` 被调用两次： | 选手程序 | 评测程序 | |---|---| | | `solve(4)` | | `get_xor(0, 1)` | 返回 `2` | | `get_xor(0, 2)` | 返回 `3` | | `get_xor(0, 3)` | 返回 `1` | | `get_xor(1, 2)` | 返回 `1` | | `get_xor(1, 3)` | 返回 `3` | | `get_xor(2, 3)` | 返回 `2` | | `return {0, 2, 3, 1}` | | | | `solve(1)` | | `return {0}` | | ### 第一次调用解释 隐藏排列为 $[2,0,1,3]$，但与它不可区分的字典序最小排列为 $[0,2,3,1]$。本次调用中 $N_1=4$，共询问 $6$ 次；由于该子任务中 $Q_1=N_1^2=16$，因此询问次数合法。 ### 第二次调用解释 当 $N_2=1$ 时，唯一可能的排列为 $[0]$。 ### 限制 - 对每个 $1\le i\le T$，均有 $1\le N_i\le 2^{20}$，其中 $N_i$ 是第 $i$ 次调用 `solve` 时的 $N$ - $1\le T\le 2^{10}$ - $T\cdot\max(N_1,N_2,\ldots,N_T)\le 2^{25}$ - 第 $i$ 次调用 `solve` 时，最多可询问 $Q_i$ 次；根据子任务不同，$Q_i$ 为 $N_i$ 或 $N_i^2$ ### 子任务 | 子任务 | 分值 | $N_i$ | $T$ | $Q_i$ | 附加限制 | |:--:|:--:|:--:|:--:|:--:|---| | 0 | 0 | - | - | $N_i^2$ | 样例。 | | 1 | 7 | $\le 2^3$ | $2^{10}$ | $N_i^2$ | - | | 2 | 18 | $\le 2^7$ | $2^5$ | $N_i^2$ | - | | 3 | 5 | $\le 2^{11}$ | $2^5$ | $N_i^2$ | - | | 4 | 5 | $\le 2^{11}$ | $2^5$ | $N_i$ | - | | 5 | 5 | $\le 2^{18}$ | $2^5$ | $N_i$ | 对某个整数 $k$，有 $N_i=2^k$。 | | 6 | 5 | $\le 2^{18}$ | $2^5$ | $N_i$ | $N_i$ 为奇数。 | | 7 | 30 | $\le 2^{18}$ | $2^5$ | $N_i$ | - | | 8 | 25 | $\le 2^{20}$ | $2^5$ | $N_i$ | - |