题目描述

这是一道交互题。

Iliyan 对 Jonas 开了一个恶作剧：他藏起了整数 $0$ 到 $N-1$ 的一个排列 $p_0,p_1,\ldots,p_{N-1}$。Jonas 很想恢复这个排列，而你答应帮助他。

Iliyan 不会直接公布排列，但同意回答如下问题：你可以选择满足 $0\le i,j<N$ 的两个下标 $i$ 和 $j$，他会告诉你 $p_i$ 与 $p_j$ 的按位异或值。

两个数的按位异或记为 $\oplus$，它会对每一对对应的二进制位执行逻辑异或。恰有一个输入位为 $1$ 时，结果位为 $1$；否则结果位为 $0$。例如，$75\oplus 29=86$，因为 $1001011_{(2)}\oplus 0011101_{(2)}=1010110_{(2)}$。在 C++ 中，a 与 b 的异或写作 a ^ b。

Iliyan 最多愿意回答 $Q$ 个问题。

然而，这些问题不一定能唯一确定隐藏排列。若对于每对满足 $0\le i,j<N$ 的下标，都有 $a_i\oplus a_j=p_i\oplus p_j$，则称排列 $a_0,a_1,\ldots,a_{N-1}$ 与 $p$ 不可区分。无论隐藏排列是 $p$ 还是 $a$，Iliyan 给出的所有回答都完全相同，因此任何询问序列都无法区分二者。$p$ 总是与自身不可区分，也可能不存在其他与它不可区分的排列。

你的任务是求出与 $p$ 不可区分的字典序最小排列。

若在排列 $x_0,x_1,\ldots,x_{N-1}$ 与 $y_0,y_1,\ldots,y_{N-1}$ 第一个不同的位置 $k$ 上有 $x_k<y_k$，则称 $x$ 的字典序小于 $y$。例如，$[2,0,1,4,3]$ 的字典序小于 $[2,0,3,1,4]$，因为它们第一个不同的位置是 $k=2$，且 $1<3$。

隐藏排列在程序开始前便已固定，不会根据你的询问发生改变。

实现细节

你需要实现以下函数：

std::vector<int> solve(int N)

• $N$：排列的元素个数。

该函数恰好调用 $T$ 次，每个隐藏排列调用一次。它必须返回与本次调用所隐藏排列不可区分的字典序最小排列。

你可以调用以下函数与评测器通信：

int get_xor(int i, int j)

每次调用返回 $p_i\oplus p_j$。两个参数都必须是合法下标，否则程序会得到 Output isn't correct: Invalid argument。该函数会在 $O(1)$ 时间内返回。

$Q$ 的值由子任务固定，不会传给你的程序。

输入格式

输入格式：

• 第 $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 被调用两次：

第一次调用解释

隐藏排列为 $[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$

子任务