#include<bits/stdc++.h> using namespace std; // #define int long long #define lson (pos<<1) #define rson (pos<<1|1) #define pii pair<int,int> #define fr first #define sc second #define mk make_pair int read(){int x=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return x*f;} const int MAXN=1000010; int n,m,q,ans,a[MAXN]; struct segtree{ pii t[MAXN<<2]; void pushup(int pos){ t[pos].fr=t[lson].fr+t[rson].fr; t[pos].sc=t[lson].sc+t[rson].sc; } void update(int pos,int l,int r,int x,int y){ if(l==r){ t[pos].fr+=x*y; t[pos].sc+=y; return; } int mid=(l+r)>>1; if(x<=mid)update(lson,l,mid,x,y); if(x>mid)update(rson,mid+1,r,x,y); pushup(pos); } pii query(int pos,int l,int r,int k){ if(l==r){ int tmp=k/l; return mk(t[pos].sc-tmp,k-tmp*l); } int mid=(l+r)>>1; if(k>=t[lson].fr)return query(rson,mid+1,r,k-t[lson].fr); else { pii tmp=query(lson,l,mid,k); return mk(tmp.fr+t[rson].sc,tmp.sc); } } void prt(int pos,int l,int r){ if(l==r){ for(int i=1;i<=t[pos].sc;i++)cout<<l<<" "; return; } int mid=(l+r)>>1; prt(lson,l,mid);prt(rson,mid+1,r); } }T[2]; set<pii>st; int b,w,bw; pii p[MAXN]; void inst(int x,int y){ // p[++cnt]= if(y)b--;else w--; auto it=st.lower_bound(mk(x,0)); pii L=mk(0,0),R=mk(0,0); if(it!=st.end())R=*it; if(it!=st.begin())it--,L=*it; // cout<<x<<" "<<y<<" "<<L.fr<<" "<<L.sc<<" "<<R.fr<<" "<<R.sc<<endl; if(L.fr&&R.fr){ if(L.sc==R.sc)T[L.sc].update(1,0,n,R.fr-L.fr-1,-1); else bw--; } if(L.fr&&L.sc==y)T[y].update(1,0,n,x-L.fr-1,1); else if(L.fr)bw++; if(R.fr&&R.sc==y)T[y].update(1,0,n,R.fr-x-1,1); else if(R.fr)bw++; st.insert(mk(x,y)); } void del(int x,int y){ if(y)b++;else w++; st.erase(mk(x,y)); auto it=st.lower_bound(mk(x,0)); pii L=mk(0,0),R=mk(0,0); if(it!=st.end())R=*it; if(it!=st.begin())it--,L=*it; if(L.fr&&L.sc==y)T[y].update(1,0,n,x-L.fr-1,-1); else if(L.fr)bw--; if(R.fr&&R.sc==y)T[y].update(1,0,n,R.fr-x-1,-1); else if(R.fr)bw--; if(L.fr&&R.fr){ if(L.sc==R.sc)T[L.sc].update(1,0,n,R.fr-L.fr-1,1); else bw++; } } int qry(){ pii t0=T[0].query(1,0,n,w),t1=T[1].query(1,0,n,b); int res=t0.fr*2+t1.fr*2+bw,B=t1.sc,W=t0.sc; if(!st.empty()){ pii L=*st.begin(),R=*st.rbegin(); if(L.sc){ if(L.fr-1&&B<L.fr-1)res++; } else{ if(L.fr-1&&W<L.fr-1)res++; } if(R.sc){ if(n-R.fr&&B-(L.sc?L.fr-1:0)<n-R.fr)res++; } else{ if(n-R.fr&&W-(L.sc?0:L.fr-1)<n-R.fr)res++; } } return res; } void slv(){ n=read(),m=read(),q=read(); for(int i=1;i<=n;i++){int x=read()&1;b+=x,w+=x^1;} while(m--){ int x=read(),y=read()&1; a[x]=y; inst(x,y); } while(q--){ int op=read(),x=read(),y=op==2?(read()&1):0; if(op==1)del(x,a[x]),a[x]=0; else a[x]=y,inst(x,y); printf("%d\n",qry()); } } signed main(){ slv(); return 0; }