4613: 瓦西里集合
内存限制：256 MB
时间限制：2 S
标准输入输出
题目类型：传统
评测方式：文本比较
上传者：
提交：1
通过：1
题目描述
作者已经写完了关于瓦西里的故事，所以这里只是一个正式的任务描述。
给定q个查询和一个集合A，初始只包含整数0。查询有三种类型:
“+ x”-将整数x添加到多集A中。
“−x”-从集合A中删除一个出现的整数x。它保证在这个查询之前，多集A中至少有一个x。
“?x”-给定整数x，需要计算其值，即整数x和集合A中的某个整数y的异或(也称为XOR)的最大值。
Multiset是一个集合，其中允许相等的元素。
Author has gone out of the stories about Vasiliy, so here is just a formal task description.
You are given q queries and a multiset A, initially containing only integer 0. There are three types of queries:
You are given q queries and a multiset A, initially containing only integer 0. There are three types of queries:
- "+ x"− add integer x to multiset A.
- "- x"− erase one occurrence of integer x from multiset A. It's guaranteed that at least one x is present in the multiset A before this query.
-
"? x"− you are given integer x and need to compute the value
, i.e. the maximum value of bitwise exclusive OR (also know as XOR) of integer x and some integer y from the multiset A.
Input
The first line of the input contains a single integer q (1≤q≤200000)− the number of queries Vasiliy has to perform.Each of the following q lines of the input contains one of three characters '+', '-' or '?' and an integer xi (1≤xi≤109). It's guaranteed that there is at least one query of the third type.
Note, that the integer 0 will always be present in the set A.
Output
For each query of the type '?' print one integer− the maximum value of bitwise exclusive OR (XOR) of integer xi and some integer from the multiset A.
Example
Input
10 + 8 + 9 + 11 + 6 + 1 ? 3 - 8 ? 3 ? 8 ? 11
Output
11 10 14 13
Note
After first five operations multiset A contains integers 0, 8, 9, 11, 6 and 1.The answer for the sixth query is integer
− maximum among integers 
, 
, 
, 
and 
.输入格式
输入
输入的第一行包含单个整数q(1≤q≤200000)−Vasiliy必须执行的查询数量。
输入的以下q行每一行都包含'+'、'-'或'?'和一个整数xi(1≤xi≤109)。可以保证至少有一个第三种类型的查询。
注意，整数0总是出现在集合A中。
输出格式
对于每个类型为'?'打印一个整数−整数xi和多集A中的某个整数的位独占或(XOR)的最大值。
输入样例 复制
10
+ 8
+ 9
+ 11
+ 6
+ 1
? 3
- 8
? 3
? 8
? 11输出样例 复制
11
10
14
13