E. XOR Again?
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Given an array $$$A_1, A_2, \ldots A_N$$$ of $$$N$$$ integers. Solve the following problem for every $$$M$$$ ($$$1 \leq M \leq N$$$):

  • Divide the array into exactly $$$M$$$ consecutive blocks.
  • The cost of each block is its bitwise XOR. The cost of division is the bitwise OR of its blocks' costs.
  • Find the minimum cost of division.
Input

The first line contains one integer $$$N \ (1 \leq N \leq 10^6)$$$. The second line consists of $$$N$$$ space-separated integers $$$A_1, A_2, \ldots, A_N$$$ ($$$0 \leq A_i \leq 10^6$$$).

Output

Print one line consisting of $$$N$$$ integers. The $$$i$$$-th integer is the answer for the problem with $$$M=i$$$.

Examples
Input
6
0 3 10 2 4 5
Output
10 10 11 11 11 15
Input
4
0 1 0 1
Output
0 0 1 1