Multiset and XORs
Problem
You have q queries and a multiset A that initially contains only the number 0. There are three types of queries:
- +x — add the number x to the multiset A.
- -x — remove one occurrence of the number x from the multiset A. It is guaranteed that at least one number x is present in the multiset at this moment.
- ? x — you are given a number x, you need to calculate the maximum bitwise exclusive OR (also known as XOR) of the number x and some number y from the multiset A.
Multiset — this is a set that allows multiple identical elements.
Input:
The first line of the input contains the number q (1 ≤ q ≤ 200000) — the number of requests Vasiliy needs to process.
Each of the following q lines of the input contains one of three characters "+", "-" or "?" and the number x
i (1 ≤ x
i ≤ 10
9). It is guaranteed that there is at least one query "?" in the input.
Note that the number 0 will always be present in the multiset.
Output:
For every request like "?" print a single integer — the maximum value of the bitwise XOR for the number x
i and any number from the multiset A.
Example:
| Input |
Output |
10
+8
+9
+11
+ 6
+ 1
? 3
- 8
? 3
? 8
? 11 |
11
10
14
13 |