#include <bits/stdc++.h> using namespace std; #define ll long long #define endl "\n" const int lim=60; int c[200030*60][2],siz[200030*60],bel[200300*60],X[200300*60],Y[200300*60],w[200300*60]; int n,q,cnt=1; ll k; int mat[200300*60]; inline void ins(ll x){ int now=1; // insert x; build up trie for(int i=lim-1;i>=0;i--){ bool p=(x>>i)&1; if(!c[now][p])c[now][p]=++cnt; now=c[now][p]; } // cout<<x<<":"<<now<<endl; } int fnt; inline void dfs(int x,int y,int d){ //search and lable for dp. if(bel[x]||bel[y])return ; if(x==0&&y==0)return; int p=++fnt; X[p]=x,Y[p]=y; mat[x]=y; mat[y]=x; if(x)bel[x]=p; if(y)bel[y]=p; if(!x||!y||d==-1)return ; if((k>>d)&1)dfs(c[x][0],c[y][1],d-1),dfs(c[x][1],c[y][0],d-1); else dfs(c[x][0],c[y][0],d-1),dfs(c[x][1],c[y][1],d-1);// when x=y should only search one,but i mark it. } inline void upd(int p,int d){ if(!p)return ; int x=X[p],y=Y[p]; if(!x||!y||d==-1){ // if x=0 or y=0,answer is another's siz // if d==-1 , if x=y,then the answer is siz[x],other wise the answer is the sum. if(x!=y) w[p]=siz[x]+siz[y]; else w[p]=max(siz[x],siz[y]); return ; } if(k>>d&1){ // k=1,then if x=y, dp from dif son,if x!=y,then sum it . if(x!=y) w[p]=w[bel[c[x][0]]]+w[bel[c[x][1]]]; else w[p]=max({siz[c[x][0]],siz[c[x][1]],w[bel[c[x][0]]]}); } else w[p]=max(w[bel[c[x][0]]],w[bel[c[x][1]]]);//k!=1,from same side if(x!=y) w[p]=max({w[p],siz[x],siz[y]});// if x!=y,the answer could be one's size. } int b[100]; inline void mod(ll x,int k){// increase x's size k int now=1; siz[now]+=k; b[lim]=now; for(int i=lim-1;i>=0;i--){ bool p=(x>>i)&1; now=c[now][p]; siz[now]+=k; b[i]=now; } // cout<<now<<"+"<<k<<endl; for(int i=0;i<=lim;i++) upd(bel[b[i]],i-1), upd(bel[mat[b[i]]],i-1);// update the dp status for x's accestor } ll a[100030]; ll x[100030],v[100300]; signed main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); // freopen("genshin.in","r",stdin); // freopen("anfang.out","w",stdout); cin>>n>>q>>k; k--; for(int i=1;i<=n;i++) cin>>a[i],ins(a[i]); for(int i=1;i<=q;i++) cin>>x[i]>>v[i],ins(v[i]); dfs(1,1,lim-1); for(int i=1;i<=n;i++) mod(a[i],1); if(k!=-1) cout<<w[bel[1]]<<endl; else cout<<1<<endl; for(int i=1;i<=q;i++){ mod(a[x[i]],-1); a[x[i]]=v[i]; mod(a[x[i]],1); if(k!=-1) cout<<w[bel[1]]<<endl; else cout<<1<<endl; } assert(siz[0]==0&&w[0]==0); cout.flush(); return 0; } /* */