Sequence and Queries 20

Time limit1sMemory limit512 MB

Summary
Maintain a multiset that starts with only 0, supporting insert, delete, and max-XOR queries where every element is XORed with x.
Level

Hard8 of 10

Topics
Trie, Bit manipulation, Greedy, Binary search
Solved
No attempts yet

Problem

There is an array A that contains exactly one zero. You must process the following queries.

  • 1 x: Add x to A.
  • 2 x: Remove x from A. If A contains more than one copy of x, delete only one copy. Every such query is guaranteed to have x present in A.
  • 3 x: XOR x with each element of A, then print the largest result.

Input

The first line gives the number of queries M (1 ≤ M ≤ 200,000). The next M lines each contain a query. Every x in the input is a positive integer no greater than 10^9.

At least one query of type 3 is given.

Output

Print the results of the queries.

Examples1

  1. Example 1

    Input
    10
1 8
1 9
1 11
1 6
1 1
3 3
2 8
3 3
3 8
3 11
    Expected output
    11
10
14
13