Let's define a new data structure - black box. A black box is a data structure that is capable of performing the following operations:
- add an integer to the black box
- delete an integer from the black box
- find the subset from the set of numbers present inside the black box which produce a maximal value after being XORed.
We will give you N queries. Each query is an addition or a deletion operation as mentioned above. After each query we ask you to find the maximal possible XOR that can be obtained by combining some of the numbers that are present in the black box.
Input Format
The first line of input contains an integer N.
Then there is a line with N integers, separated with single spaces. Some of the integers are positive while some are negative.
Let's denote the ith such integer by Ai. If it's positive, then it corresponds to the addition operation: addition of Ai to the black box. Otherwise, it corresponds to the deletion operation: deletion of |Ai| from the black box.
It is guaranteed that:
- we will never add a number that is already present in the black box.
- we will never delete a number that is currently not present in the black box.
Output Format
After each query, output the maximal XOR in a new line. If the black box has no numbers after the query, output 0
.
Constraints
1 ≤ N ≤ 5 * 105
0 < |Ai| ≤ 2 * 109
Sample Input
6 1 2 3 4 -2 -3
Sample Output
1 3 3 7 7 5
Explanation
- 1st Operation A = [1], maximum XOR is 1.
- 2nd Operation A = [1,2], maximum XOR is 1⊕2 = 3
- 3rd Operation A = [1,2,3], maximum XOR is 1⊕2 or 3 = 3
- 4th Operation A = [1,2,3,4], maximum XOR is 4⊕3 = 7
- 5th Operation A = [1,3,4], maximum XOR is 4⊕3 = 7
- 6th Operation A = [1,4], maximum XOR is 4⊕1 = 5
TimeLimit
The timelimits for this challenge is given here, there might be chances of some submissions written in python TLEing post rerun on additional testcases, we will provide scores on a per submission basis if such a situation arises.