题目描述

给定长度为 $N$ 的数列 $a$，其中第 $i$ 个元素为 $a_i$。niwangu 将要对数列 $a$ 进行如下操作。

• 操作：选择满足条件 $1<i<N$ 的 $i$ ，将 $a_{i-1}$ 替换为 $a_{i-1} \textup{XOR} a_i$，将 $a_{i+1}$ 替换为 $a_{i+1} \textup{XOR} a_i$。此处的 $XOR$ 表示按位异或。

请输出数列 $a$ 进行至少一次操作后得到的数列中，字典序最小的一个。

数据范围

• $1\le N\le 10^5$
• $0\le a_i\le 10^9$
• 输入全部是整数

输入

输入按照如下格式。第一行为数列长度 $N$。第二行为 $N$ 个整数，其中第 $i$ 个整数为 $a_i$。

测试用例

测试用例 1

输入

3
2 3 1

输出

1 3 2

解说

进行一次操作后，$(2, 3, 1)$ 变为 $(2\textup{XOR}3, 3, 1\textup{XOR}3)=(1, 3, 2)$

测试用例 2

输入

5
1 1 3 2 1

输出

0 1 0 2 3

测试用例 3

15
454149310 980904516 263802120 650414794 570152508 496610001 940998475 895836185 33049807 966544922 733719158 536712208 292230877 949871052 342421559

输出

23988306 158687594 74711974 280079291 131007899 572247609 33049807 210457501 22094817 292230877 86347283 143004158 53812512 67781078 644469472