Problem Description

For a permutation $\{p_n\}$ of $1 \sim n$, define its XOR-generated sequence as a non-negative integer sequence $\{b_{n - 1}\}$ of length $n - 1$, generated as follows:

Here, $\operatorname{xor}$ denotes the bitwise XOR operation. In C++, it is represented by the ^ operator.

Given $n$ and $\{b_{n - 1}\}$, you need to construct a corresponding permutation $\{p_n\}$.

The input guarantees that a solution exists. If multiple solutions exist, output any one.

Input Format

This problem contains multiple test cases in a single test file.

The first line contains a positive integer $T$, representing the number of test cases.

For each test case:

• The first line contains a positive integer $n$.

• The second line contains $n - 1$ non-negative integers, representing the XOR-generated sequence $\{b_{n - 1}\}$.

Output Format

For each test case, output one line with $n$ positive integers, representing a corresponding permutation $\{p_n\}$. If multiple solutions exist, output any one.

2
4
1 2 5
6
1 7 3 2 5

2 3 1 4
3 2 5 6 4 1

Hint

[Sample Explanation]

For the first test case, we have:

• $b_1 = p_1 \operatorname{xor} p_2 = 2 \operatorname{xor} 3 = 1$
• $b_2 = p_2 \operatorname{xor} p_3 = 3 \operatorname{xor} 1 = 2$
• $b_3 = p_3 \operatorname{xor} p_4 = 1 \operatorname{xor} 4 = 5$

Therefore, the resulting sequence $b$ is the same as the input, so this permutation satisfies the requirement.

For the second test case, $[4,5,2,1,3,6]$ is also a valid permutation.

[Constraints]

This problem uses bundled tests.

For $100\%$ of the data:

• $2 \le n \le 2 \times 10^6$;
• $1 \le T \le 10^6$;
• $\sum n \le 2 \times 10^6$;
• It is guaranteed that at least one valid solution exists.

The detailed subtask distribution is as follows:

[Notes]

The input file for this problem is large. Please use a faster input method.

Translated by ChatGPT 5