Problem Description

Given a sequence $a$ of length $N$, where the $i$-th element is $a_i$.

Niwango can perform the following operation on $a$ zero or more times:

• Operation: Choose an integer $i$ such that $1 < i < N$, and replace $a_{i-1}$ with $a_{i-1} \text{ XOR } a_{i}$, and $a_{i+1}$ with $a_{i+1} \text{ XOR } a_{i}$. Here, $\text{XOR}$ denotes the bitwise exclusive OR operation.

Find the lexicographically smallest sequence that can be obtained after performing zero or more operations.

Input Format

The input is given from the standard input in the following format:

$N$ $a_1$ $a_2$ $...$ $a_N$

Output Format

Output the answer.

Sample Input and Output

Sample Input #1

3
2 3 1

Sample Output #1

1 3 2

Sample Input #2

5
1 1 3 2 1

Sample Output #2

0 1 0 2 3

Sample Input #3

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

Sample Output #3

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

Notes/Hints

Constraints

• $1 \leq N \leq 10^5$
• $0 \leq a_i \leq 10^9$
• All given inputs are integers

Sample Explanation 1

• With one operation, $(2, 3, 1) \rightarrow (2 \text{ XOR } 3, 3, 1 \text{ XOR } 3) = (1, 3, 2)$.

见题面 Input 部分

见题面 Output 部分