J. Juiceless Class
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Pedro Vieira is a student at the Institute of Many Equations, commonly referred to as IME. He's attending a class hosted by none other than the infamous Mr. Potato and since his class is soooooo boring (really, it is), Pedro begins making up random algorithms and running them in his mind (as one commonly does).

On one beautiful morning, he overheard Mr. Potato talking some nonsense about XOR operations, and so, tried to come up with an algorithm that does the following: given an array of integers, find the greatest value that can be obtained from XOR-ing a subset of this array. Since this is too easy, he reformulated the problem. Given an array $$$a$$$ of $$$n$$$ elements, for every $$$i$$$ from $$$1 ... n$$$, find the maximum XOR value of a subset of the array $$$(a_1, a_2, ..., a_i)$$$.

Input

The first line of the input contains a single integer, $$$n$$$, $$$(1 \leq n \leq 10^6)$$$ — the amount of elements in the array.

The second line contains $$$n$$$ integers $$$a_i$$$, $$$(0 \leq a_i \lt 2^{63})$$$ — the array $$$a$$$.

Output

Output $$$n$$$ integers in a single line, each one separated by a space, indicating the maximum value of applying the XOR operation over a subset of the array $$$(a_1, a_2, ..., a_i)$$$.

Examples
Input
5
4 3 5 2 19
Output
4 7 7 7 23
Input
7
392 17179869184 229 1128 44439 12283 1337
Output
392 17179869576 17179869576 17179870688 17179913623 17179913623 17179913643