題干：

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:

"+ 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.

Multiset is a set, where equal elements are allowed.

Input

The first line of the input contains a single integer?q?(1?≤?q?≤?200?000)?— 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?.

題目大意：

維護一個初始時只有元素0的多重集，有三種操作

1? x: 添加一個數(shù)x

2? x: 刪除一個數(shù)x

3? x: 詢問一個數(shù)x與這個集合中的某一個元素的異或值最大是多少。

總共q次操作，每次操作是xi? (1?≤?xi?≤?1e9,1?≤?q?≤?200?000)

解題報告：

直接01字典樹，注意剛開始需要先插入0.再就是數(shù)組需要開大一些左右，2e5是不夠的。

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<stack> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define FF first #define SS second #define ll long long #define pb push_back #define pm make_pair using namespace std; typedef pair<int,int> PII; const int MAX = 1e7 + 5; int tr[MAX][2],tot,num[MAX]; void ins(int x) {int rt = 0;for(int bit = 31; bit>=0; bit--) {int tar = (x&(1<<bit)) > 0 ? 1 : 0;if(tr[rt][tar] == 0) tr[rt][tar] = ++tot;rt=tr[rt][tar]; num[rt]++;} } void del(int x) {int rt = 0;for(int bit = 31; bit>=0; bit--) {int tar = (x&(1<<bit)) > 0 ? 1 : 0;rt=tr[rt][tar]; num[rt]--;} } int cal(int x) {int res = 0,rt = 0;for(int bit = 31; bit>=0; bit--) {int tar = (x&(1<<bit)) > 0 ? 1 : 0;if(num[tr[rt][!tar]] > 0) res |= (1<<bit),rt=tr[rt][!tar];else rt = tr[rt][tar];if(rt == 0) break;} return res; } int main() {int q,x; char op[5];cin>>q;ins(0);while(q--) {scanf("%s%d",op,&x);if(op[0] == '+') ins(x);if(op[0] == '-') del(x);if(op[0] == '?') printf("%d\n",cal(x));}return 0 ; }

?

總結(jié)

以上是生活随笔為你收集整理的【CodeForces - 706D】Vasiliy's Multiset（01字典树）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。