#include<bits/stdc++.h> using namespace std; //#define int long long #define ll long long #define endl "\n" #define lc(x) T[x].c[0] #define rc(x) T[x].c[1] int n,m; int lim=60; struct node{ int c[2]={-1,-1},siz; }T[400300*60]; ll k; int cnt; int F[600300*60]; int fa[600300*60]; int id; int I[600300*60]; int dp[600300*60]; pair<int,int> P[600300*60]; bitset<600300*60>vis; inline int g(int x,int y){ if(x==-1&&y==-1)return 0; if(x==-1)return y; if(y==-1)return x; return I[x]; } inline bool upd(int d,int x,int y){ int p=g(x,y); int pre=F[p]; if(d==-1){ if(x!=y) F[p]=F[x]+F[y]; else F[p]=F[x]; } else if(x==y){ if((k>>d)&1){ F[p]=F[g(lc(x),rc(x))]; } else{ int l=lc(x)==-1?0:lc(x); int r=rc(x)==-1?0:rc(x); F[p]=max(F[g(lc(x),lc(x))],F[g(rc(x),rc(x))]); } } else { int l=lc(x)==-1?0:lc(x); int r=rc(x)==-1?0:rc(x); if((k>>d)&1) F[p]=F[g(rc(x),lc(y))]+F[g(lc(x),rc(y))]; else { F[p]=max({F[g(rc(x),rc(y))],F[g(lc(x),lc(y))],F[x],F[y]}); } } // cout<<x<<' '<<y<<' '<<pre<<' '<<F[p]<<endl; return pre!=F[p]; } inline int f(int d,int x,int y){ // cout<<d<<' '<<x<<' '<<y<<endl; if(x==-1&&y==-1)return 0; if(x==-1)return y; if(y==-1)return x; int p=++id; I[x]=p; dp[p]=d; P[p]={x,y}; // cerr<<d<<' '<<x<<' '<<y<<" "<<p<<endl<<endl; // ct[x]++,assert(ct[x]<=1); //if(x!=y) //ct[y]++,assert(ct[y]<=1); if(d==-1){ if(x!=y) F[p]=F[x]+F[y]; else F[p]=F[x]; fa[x]=fa[y]=p;return p;} int res=0; if(x==y){ if((k>>d)&1){ int w=f(d-1,lc(x),rc(x)); fa[w]=p; F[p]=F[w]; } else{ int a=f(d-1,lc(x),lc(x)),b=f(d-1,rc(x),rc(x)); fa[a]=fa[b]=p; F[p]=max(F[a],F[b]); } } else { if((k>>d)&1){ int a=f(d-1,rc(x),lc(y)),b=f(d-1,lc(x),rc(y)); fa[a]=fa[b]=p; F[p]=F[a]+F[b]; } else { int a=f(d-1,rc(x),rc(y)),b=f(d-1,lc(x),lc(y)); fa[a]=fa[b]=p; fa[x]=fa[y]=p; F[p]=max({F[a],F[b],F[x],F[y]}); } } return p; } inline void ins(ll x,int k){ int now=0; //cout<<x<<":::"; for(int d=lim;d>=0;d--){ if(T[now].c[(x>>d)&1]==-1)T[now].c[(x>>d)&1]=++cnt; now=T[now].c[(x>>d)&1]; T[now].siz+=k; F[now]+=k; // cout<<now<<' '; } // cout<<endl; } inline int fd(ll x){ int now=0; for(int d=lim;d>=0;d--) now=T[now].c[(x>>d)&1]; return now; } queue<int>q[65]; int rt; inline void upd(ll x,int k){ int now=0; for(int d=lim;d>=0;d--){ if(T[now].c[(x>>d)&1]==-1)T[now].c[(x>>d)&1]=++cnt; now=T[now].c[(x>>d)&1]; T[now].siz+=k; F[now]+=k; if(fa[now]==-1)continue; vis[fa[now]]=1; q[dp[fa[now]]+1].push(fa[now]); } for(int i=0;i<=lim+3;i++){ while(!q[i].empty()){ int x=q[i].front(); q[i].pop(); //us|=P[x].first==0&&P[x].second==0; //cerr<<x<<' '<<dp[x]<<' '<<i<<' '<<P[x].first<<' '<<P[x].second<<endl; //cout<<P[x].first<<" "<<P[x].second<<endl<<endl; vis[x]=0; if(!upd(dp[x],P[x].first,P[x].second))continue; if(fa[x]!=-1&&!vis[fa[x]]) q[dp[fa[x]]+1].push(fa[x]),vis[fa[x]]=1; } } //cerr<<us<<' '<<F[rt]<<endl; } ll a[400300]; vector<pair<int,ll>>ASK; signed main(){ // freopen("xor.in","r",stdin); // freopen("xor.out","w",stdout); ios::sync_with_stdio(0); const ll V=(1ll<<60); memset(fa,-1,sizeof(fa)); I[0]=0; for(int i=0;i<=cnt;i++) T[i].c[0]=T[i].c[1]=-1,T[i].siz=0; for(int i=0;i<=id;i++) F[i]=0,fa[i]=-1; cnt=0; cin>>n>>m>>k; for(int i=1;i<=n;i++){ cin>>a[i]; ins(a[i],1); assert(a[i]<V); } ASK.clear(); for(int i=1;i<=m;i++){ int x; ll y; cin>>x>>y; assert(y<V); ins(y,0); ASK.push_back({x,y}); } id=cnt; for(int i=1;i<=cnt;i++) F[i]=T[i].siz; rt=f(lim,0,0); //cout<<F[rt]<<endl; //return 0; cout<<F[rt]<<endl; for(int i=1;i<=m;i++){ int x=ASK[i-1].first; ll y=ASK[i-1].second; upd(a[x],-1); //cout<<x<<' '<<y<<endl; a[x]=y; upd(a[x],1); //for(int i=0;i<=id;i++) //F[i]=0,fa[i]=-1; //id=cnt; // for(int i=1;i<=cnt;i++) //F[i]=T[i].siz; //f(lim,0,0); cout<<F[rt]<<endl; } cout.flush(); return 0; }