#include<bits/stdc++.h> #define up(i,l,r) for(int i=(l);i<=(r);++i) #define down(i,l,r) for(int i=(l);i>=(r);--i) #define pi pair<int,int> #define p1 first #define p2 second #define p_b push_back #define m_p make_pair #define ppc __builtin_popcount using namespace std; typedef long long ll; const int maxn=1e6+10; inline ll read(){ ll x=0;short t=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')t=-1;ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*t; }int n,q;ll k; struct node { int ls,rs,siz; }d[maxn*6]; int rt=1,ct=1; #define ls(p) d[p].ls #define rs(p) d[p].rs #define siz(p) d[p].siz bool vis[maxn*6];vector<int>A; void ins(ll &x,int c){ int p=rt;siz(p)+=c; vis[p]=1,A.p_b(p); down(i,59,0){ if((x>>(ll)i)&1){ if(!rs(p))rs(p)=++ct;p=rs(p); }else { if(!ls(p))ls(p)=++ct;p=ls(p); }siz(p)+=c; vis[p]=1,A.p_b(p); } }int dp(int x,int y,int dep); int g(int x,int y,int dep){ return max(max(siz(x),siz(y)),dp(x,y,dep)); } map<pi,int>mp; int dp(int x,int y,int dep){ if((!x)||(!y))return mp[m_p(x,y)]=siz(x|y); if(dep==-1)return mp[m_p(x,y)]=((x==y)?siz(x):siz(x)+siz(y)); if((k>>(ll)dep)&1){ if(x==y){ return mp[m_p(x,y)]=g(ls(x),rs(x),dep-1); } int res=0; res+=g(ls(x),rs(y),dep-1); res+=g(rs(x),ls(y),dep-1); return mp[m_p(x,y)]=res; }return mp[m_p(x,y)]=max(dp(ls(x),ls(y),dep-1),dp(rs(x),rs(y),dep-1)); } int getdp(int x,int y,int dep); int gg(int x,int y,int dep){ return max(max(siz(x),siz(y)),getdp(x,y,dep)); } int getdp(int x,int y,int dep){ if((!vis[x])&&(!vis[y]))return mp[m_p(x,y)]; if((!x)||(!y))return mp[m_p(x,y)]=siz(x|y); if(dep==-1)return mp[m_p(x,y)]=((x==y)?siz(x):siz(x)+siz(y)); if((k>>(ll)dep)&1){ if(x==y){ return mp[m_p(x,y)]=gg(ls(x),rs(x),dep-1); } int res=0; res+=gg(ls(x),rs(y),dep-1); res+=gg(rs(x),ls(y),dep-1); return mp[m_p(x,y)]=res; }return mp[m_p(x,y)]=max(getdp(ls(x),ls(y),dep-1),getdp(rs(x),rs(y),dep-1)); } ll a[maxn]; struct nd { int x;ll v; }T[maxn]; void slv(){ n=read(),q=read(),k=read()-1; if(k==-1){ up(i,1,q+1)printf("0\n"); return; } up(i,1,n)a[i]=read(),ins(a[i],1); up(i,1,q)T[i].x=read(),T[i].v=read(),ins(T[i].v,1),ins(T[i].v,-1); memset(vis,0,sizeof(vis));A.clear(); printf("%d\n",dp(1,1,59)); up(i,1,q){A.clear(); int x=T[i].x; ins(a[x],-1);a[x]=T[i].v;ins(a[x],1); printf("%d\n",getdp(1,1,59)); for(int y:A)vis[y]=0; } }int main(){ //freopen("anfang.in","r",stdin); //freopen("anfang.out","w",stdout); slv(); fclose(stdin); fclose(stdout); return 0; }