Set and Queries

Time limit4sMemory limit512 MB

Summary

After each insertion or deletion in a set of up to 500,000 integers, report the maximum XOR achievable by any subset of the current set.

Level: Hard8 of 10
Topics: Bit manipulation, Math, Greedy, Divide and conquer
Solved: No attempts yet

Problem

You must perform the following queries on a set $S$ .

x: add $x$ to the set $S$ .
-x: remove $x$ from the set $S$ .

After each query, find the subset $T$ of $S$ whose XOR of all elements is the largest.

Input

The first line gives the number of queries $N$ ( $1 \le N \le 500{,}000$ ). The following $N$ lines give one query each. Every number added to the set is a positive integer less than or equal to $2{,}000{,}000{,}000$ .

The input never contains a query that adds a number already in the set or a query that removes a number not in the set.

Output

After each query, print the XOR of all elements of $T$ . If the size of the set $S$ is $0$ after a query, print $0$ .

Examples2

Example 1
Input
```
6
1
2
3
4
-2
-3
```
Expected output
```
1
3
3
7
7
5
```
Example 2
Input
```
5
1
-1
2
-2
3
```
Expected output
```
1
0
2
0
3
```