P11008 『STA - R7』XOR-Generated Sequence

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: $$b_i = p_i \operatorname{xor} p_{i + 1}$$ 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.

**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}\}$.

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

**[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: |Subtask ID|Constraints|Score| |:--------:|:--------:|:--------:| |1|$\sum n^2 \le 2 \times 10^6$|$17$| |2|$2 \nmid n$|$23$| |3|$4 \mid n$|$26$| |4|No special constraints|$34$| **[Notes]** The input file for this problem is large. Please use a faster input method. Translated by ChatGPT 5