题目描述

对于一个 $1 \sim n$ 的排列 $\{p_n\}$，定义其异或生成序列为一个长度为 $n - 1$ 的非负整数序列 $\{b_{n - 1}\}$，按如下方式生成：

其中 $\operatorname{xor}$ 代表按位异或运算。在 C++ 语言中由 ^ 运算符表示。

给定 $n, \{b_{n - 1}\}$，你需要构造一个对应的排列 $\{p_n\}$。

输入数据保证有解，如果存在多个解，输出任意一个即可。

输入格式

本题单个测试点内含有多组测试数据。

第一行一个正整数 $T$，代表测试数据组数。

对于每组测试数据，

• 第一行一个正整数 $n$。

• 第二行 $n - 1$ 个非负整数，代表异或生成序列 $\{b_{n - 1}\}$。

输出格式

对于每组测试数据，输出一行 $n$ 个正整数，代表一个对应的排列 $\{p_n\}$。如果存在多个解，输出任意一个即可。

2
4
1 2 5
6
1 7 3 2 5

2 3 1 4
3 2 5 6 4 1

提示

【样例解释】

对于第一组测试数据，我们有：

• $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$

因此得到的 $b$ 序列和输入中的相同，进而该排列符合要求。

对于第二组测试数据，$[4,5,2,1,3,6]$ 也是一个符合要求的排列。

【数据范围】

本题采用捆绑测试。

对于 $100\%$ 的数据：

• $2 \le n \le 2 \times 10^6$；
• $1 \le T \le 10^6$；
• $\sum n \le 2 \times 10^6$;
• 保证至少存在一个合法的解。

具体部分分分配如下：

【提示】

本题输入文件较大，请使用较为快速的输入方式。