问题描述

给定一个长度为 $N$ 的数列 $a$，其中第 $i$ 个元素为 $a_i$。

对于数列 $a$，尼玛君可以执行以下操作零次或多次：

• 操作：选择满足 $1 < i < N$ 的整数 $i$，将 $a_{i-1}$ 替换为 $a_{i-1} \oplus a_i$，将 $a_{i+1}$ 替换为 $a_{i+1} \oplus a_i$。其中 $\oplus$ 表示异或运算。

请找出在执行零次或多次操作后得到的数列 $a$ 中字典序最小的那个数列。

约束条件

• $1 \leq N \leq 10^5$
• $0 \leq a_i \leq 10^{9}$
• 输入都是整数。

输入

输入由标准输入给出，具有以下格式。

$N$ $a_1$ $a_2$ $...$ $a_{N}$

输出

请输出结果。

示例1

3
2 3 1

输出示例1

1 3 2

• 可以通过一次操作将 $(2,3,1) \rightarrow (2 \oplus 3, 3, 1 \oplus 3) = (1,3,2)$。

示例2

5
1 1 3 2 1

输出示例2

0 1 0 2 3

示例3

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

输出示例3

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