111111111111111

Time limit2.5sMemory limit1024 MB

Summary

For each prefix of N given integers, find the maximum popcount of the XOR of some subset of those integers, and print one such XOR value per day.

Level: Medium7 of 10
Topics: Bit manipulation, Math, Brute force
Solved: No attempts yet

Problem

Runos who work at AI Network use binary numbers, and they like numbers whose binary representation has many $1$ s.

AIN manages the runos. To motivate them, AIN wants to give the "Runo of the Day" award each day for the next $N$ days to the runo who worked hardest that day. The prize is a number whose binary representation has many $1$ s, the kind of number runos are likely to like.

AIN found that choosing a number by hand is hard, so AIN subscribed to a service that delivers one integer per day for the next $N$ days. Let $V_i$ be the number delivered on day $i$ .

Each day, AIN looks at the numbers collected so far and makes the prize as follows.

If today is day $i$ of the subscription, pick any subset of $V_1, V_2, \cdots, V_i$ . AIN may pick none of them or all of them.
Compute the bitwise XOR of all picked numbers. If no number is picked, the result is $0$ . If exactly one number is picked, the result is that number.

AIN chooses, as the prize, the number with the most $1$ s in its binary representation among all numbers that can be made this way.

For each of the next $N$ days, find one number that AIN can choose as the prize that day.

Input

The first line contains $N$ , the number of days for the award and the number of days the delivery service is subscribed.

Each of the next $N$ lines contains one integer delivered by the service. The integer on the $i$ -th line is $V_i$ .

Output

Print $N$ lines. On the $i$ -th line, print one number that AIN can choose as the prize on day $i$ .

Constraints

$1 \leq N \leq 111$
$0 \leq V_i \leq 111\,111\,111\,111\,111$

Examples3

Example 1
Input
```
2
3
5
```
Expected output
```
3
6
```
Example 2
Input
```
3
6
14
9
```
Expected output
```
6
14
15
```

Example 3

Input

Expected output

1010000000
1010000110
1010000111