题目描述

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<N$, and he tells you the bitwise XOR of $p_i$ and $p_j$.

The bitwise XOR of two numbers, denoted by $\oplus$, performs logical exclusive OR on every pair of corresponding bits. A result bit is $1$ if exactly one input bit is $1$, and $0$ otherwise. For example, $75\oplus 29=86$ because $1001011_{(2)}\oplus 0011101_{(2)}=1010110_{(2)}$. In C++, the XOR of a and b is written a ^ b.

Iliyan is willing to answer at most $Q$ questions.

These questions cannot always determine the hidden permutation uniquely. A permutation $a_0,a_1,\ldots,a_{N-1}$ is indistinguishable from $p$ if $a_i\oplus a_j=p_i\oplus p_j$ for every pair $0\le i,j<N$. Every answer is identical whether the hidden permutation is $p$ or $a$, so no sequence of questions can distinguish them. The permutation $p$ is always indistinguishable from itself, and there may be no other such permutation.

Your task is to find the lexicographically smallest permutation indistinguishable from $p$.

A permutation $x_0,x_1,\ldots,x_{N-1}$ is lexicographically smaller than $y_0,y_1,\ldots,y_{N-1}$ if, at the first position $k$ where they differ, $x_k<y_k$. For example, $[2,0,1,4,3]$ is lexicographically smaller than $[2,0,3,1,4]$ because their first difference is at $k=2$ and $1<3$.

The hidden permutation is fixed before your program starts and does not change in response to your questions.

Implementation details

Implement the following function:

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

• $N$: the number of elements in the permutation.

This function is called exactly $T$ times, once for each hidden permutation. It must return the lexicographically smallest permutation indistinguishable from the permutation hidden for that call.

To communicate with the jury, you may call:

int get_xor(int i, int j)

Each call returns $p_i\oplus p_j$. Both arguments must be valid indices. Otherwise, your solution receives Output isn't correct: Invalid argument. The function responds in constant time $O(1)$.

The value of $Q$ is fixed for each subtask and is not passed to your program.

输入格式

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)
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		-		$N_i^2$	The example.
1	7	$\le 2^3$	$2^{10}$		-
2	18	$\le 2^7$	$2^5$
3	5	$\le 2^{11}$
4				$N_i$
5		$\le 2^{18}$			$N_i=2^k$ for some integer $k$.
6					$N_i$ is odd.
7	30				-
8	25	$\le 2^{20}$