D. Vitya and Strange Lesson

Today at the lesson Vitya learned a very interesting function — mex. Mex of a sequence of numbers is the minimum non-negative number that is not present in the sequence as element. For example,mex([4, 33, 0, 1, 1, 5]) = 2 and mex([1, 2, 3]) = 0.

Vitya quickly understood all tasks of the teacher, but can you do the same?

You are given an array consisting of n non-negative integers, andm queries. Each query is characterized by one numberx and consists of the following consecutive steps:

Perform the bitwise addition operation modulo 2 (xor) of each array element with the numberx. Find mex of the resulting array.

Note that after each query the array changes.

Input

First line contains two integer numbers n andm (1 ≤ n, m ≤ 3·10⁵) — number of elements in array and number of queries.

Next line contains n integer numbers a_i (0 ≤ a_i ≤ 3·10⁵) — elements of then array.

Each of next m lines contains query — one integer numberx (0 ≤ x ≤ 3·10⁵).

Output

For each query print the answer on a separate line.

Examples Input 2 2 1 3 1 3 Output 1 0 Input 4 3 0 1 5 6 1 2 4 Output 2 0 0 Input 5 4 0 1 5 6 7 1 1 4 5 Output 2 2 0 2 cf的d题，看题解都看了好久，主要是太弱了。 思路来自harlow_cheng 感谢 题意：给你一个数列，然后给你一个数字k，让你对数列中的每一个数字异或k，之后求出新数列中没出现过的最小自然数。 由于异或运算具有结合性，所以a^b^c^d=a^(b^c^d),所以你没有必要数组进行更新。 如果说给你一个值K，那么你对给定数列a中的元素进行异或k，将会得到一个新的数列A，同时我们定义b是a数列中没有出现过的自然数，这时我们再对b进行异或k，我们将得到一个B数列。B中的元素与A中的元素依旧存在如同b与a之间的关系，即B中的元素是A中未出现过的自然数。 明白了以上道理我们就可以把A全部插入01字典树，然后求一个异或k最小的数值就可以了。 AC代码如下，来自mengxiang000000 感谢 #include<stdio.h> #include<string.h> #include<map> #include<algorithm> #include<math.h> #include<stdlib.h> using namespace std; #define ll long long int #define maxn 2 typedef struct tree { tree *nex[maxn]; ll v; ll val; } tree; tree root; void init() { for(ll i=0; i<maxn; i++) { root.nex[i]=NULL; root.v=0; root.val=0; } } void creat(char *str,int va) { int len=strlen(str); tree *p=&root,*q; for(int i=0; i<len; i++) { int id=str[i]-'0'; if(p->nex[id]==NULL) { q=(tree *)malloc(sizeof(root)); q->v=1; for(int j=0; j<2; j++) { q->nex[j]=NULL; } p->nex[id]=q; } else { p->nex[id]->v++; } p=p->nex[id]; if(i==len-1) { p->val=va; } } } void find(char *str,ll query) { ll len=strlen(str); tree *p=&root; for(ll i=0; i<len; i++) { ll id=str[i]-'0'; if(p->nex[id]!=NULL) { p=p->nex[id]; } else p=p->nex[1-id]; if(p==NULL)return ; } printf("%lld\n",p->val^query); } int main() { ll n,q; while(~scanf("%lld%lld",&n,&q)) { init(); map<ll,ll>s; for(ll i=1; i<=n; i++) { ll x; scanf("%lld",&x); if(s[x]==0) { s[x]=1; } } for(ll i=0; i<=600000; i++) { if(s[i]==0) { char ss[25]; ll x=i; ss[21]='\0'; for(int j=20; j>=0; j--) { if(x) { ss[j]=x%2+'0'; x/=2; } else { ss[j]='0'; } } creat(ss,i); } } ll temp=0; while(q--) { ll x; scanf("%lld",&x); temp^=x; x=temp; char ss[25]; ss[21]='\0'; for(int j=20; j>=0; j--) { if(x) { ss[j]=x%2+'0'; x/=2; } else { ss[j]='0'; } } find(ss,temp); } } }