• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

A $k$-partition of an array means dividing the array into groups of $k$ elements. The first $k$ elements go in the first group, the next $k$ elements in the second group, and so on... If there are fewer than $k$ elements left at the end, place all remaining elements in the final group.

For example, if the initial array is $[3, 0, 2, 1, 2]$ and $k=2$, the grouping would be $[[3, 0], [2, 1], [2]]$

The score of a group is defined as the bitwise XOR sum of its elements. For example, the score of the group [3,0] is $3$, the score of the group [2,1] is $3$, and the score of the group [2] is $2$. The score of the entire array is the bitwise AND of the scores of all its groups. For the grouping above, the total score of the array is: 3 AND 3 AND 2 = 2.

for each $k$ as $1, 2, 3, ..., n$, calculate the score for a fixed array.

input

The first line of input contains a positive integer n, the number of elements in the array. $$1 \leq n \leq 10^6$$ The second line contains n integers $a_1, a_2, \dots, a_n,$ separated by spaces.

$$0 \leq a_i \leq 10^9$$

output

Print a single line containing the total scores of the array for $k = 1, 2, \dots, n$ separated by spaces.

example

sample input 1

4
1 2 3 4

sample output 1

0 3 0 4

sample input 2

5
3 0 2 1 2

sample output 2

0 2 1 0 2