P17272 [eJOI 2026] XORting

*This is an interactive problem.* Iliyan has played a prank on Jonas: he has hidden a permutation $p_0,p_1,\ldots,p_{N-1}$ of the integers from $0$ to $N-1$. Jonas is desperate to recover it, and you have agreed to help him. Iliyan will not reveal the permutation outright, but he will answer questions of the following kind: choose two indices $i$ and $j$ with $0\le i,j

Input format: - line $1$: two integers $T$ and $Q_{\mathrm{type}}$, where $Q_{\mathrm{type}}$ is either $1$ or $2$; - the following $2T$ lines describe the tests: - line $2i$: one integer $N_i$; - line $2i+1$: $N_i$ integers $p_0,p_1,\ldots,p_{N_i-1}$. If $Q_{\mathrm{type}}=1$, then $Q_i=N_i$; if $Q_{\mathrm{type}}=2$, then $Q_i=N_i^2$.

Output format: - line $i$: the permutation returned by your program on the $i$-th test.

### Example Consider the following interaction, in which `solve` is called twice: | Participant program | Jury program | |---|---| | | `solve(4)` | | `get_xor(0, 1)` | returns `2` | | `get_xor(0, 2)` | returns `3` | | `get_xor(0, 3)` | returns `1` | | `get_xor(1, 2)` | returns `1` | | `get_xor(1, 3)` | returns `3` | | `get_xor(2, 3)` | returns `2` | | `return {0, 2, 3, 1}` | | | | `solve(1)` | | `return {0}` | | ### Explanation of the first call The hidden permutation is $[2,0,1,3]$, but the lexicographically smallest indistinguishable permutation is $[0,2,3,1]$. Six questions were asked for $N_1=4$, which is allowed because $Q_1=N_1^2=16$ in this subtask. ### Explanation of the second call The only possible permutation for $N_2=1$ is $[0]$. ### Constraints - $1\le N_i\le 2^{20}$ for every $1\le i\le T$, where $N_i$ is the value of $N$ in the $i$-th call to `solve` - $1\le T\le 2^{10}$ - $T\cdot\max(N_1,N_2,\ldots,N_T)\le 2^{25}$ - During the $i$-th call to `solve`, you may ask at most $Q_i$ questions, where $Q_i$ is either $N_i$ or $N_i^2$, depending on the subtask ### Subtasks | Subtask | Points | $N_i$ | $T$ | $Q_i$ | Additional constraints | |:--:|:--:|:--:|:--:|:--:|---| | 0 | 0 | - | - | $N_i^2$ | The example. | | 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$ | $N_i=2^k$ for some integer $k$. | | 6 | 5 | $\le 2^{18}$ | $2^5$ | $N_i$ | $N_i$ is odd. | | 7 | 30 | $\le 2^{18}$ | $2^5$ | $N_i$ | - | | 8 | 25 | $\le 2^{20}$ | $2^5$ | $N_i$ | - |