← 返回题目列表

Codeforces · 1895/D

D. 异或构造

中文机器翻译题面 查看原题

给你 $$$n-1$$$ 整数 $$$a_1, a_2, \dots, a_{n-1}$$$。

你的任务是构造一个数组 $$$b_1, b_2, \dots, b_n$$$ 使得:

- 从 $$$0$$$ 到 $$$n-1$$$ 的每个整数在 $$$b$$$ 中只出现一次;
- 对于从 $$$1$$$ 到 $$$n-1$$$ 的每个 $$$i$$$,$$$b_i \oplus b_{i+1} = a_i$$$ (其中 $$$\oplus$$$ 表示按位异或运算符)。

输入

第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$)。

第二行包含 $$$n-1$$$ 整数 $$$a_1, a_2, \dots, a_{n-1}$$$ ($$$0 \le a_i \le 2n$$$)。

对输入的附加约束:始终可以从给定序列 $$$a$$$ 构造至少一个有效数组 $$$b$$$。

输出

打印 $$$n$$$ 整数 $$$b_1, b_2, \dots, b_n$$$。如果有多个这样的数组,您可以打印其中任何一个。

示例

输入 #1

4
2 1 2

输出 #1

0 2 3 1

输入 #2

6
1 6 1 4 1

输出 #2

2 3 5 4 0 1