掃除 (Sweeping)
sol
从 Subtask 3 的特殊性质入手，可以发现一个关键性质：无论之后如何操作，这个单调性在任何时刻均满足。其原因可以简单考虑一下操作的效力范围与结果得到。
理解之后容易推广到全局，不难发现所有被操作过的点形成的点集满足上述性质。满足此性质的话，每次操作作用到的点都是一个连续区间，且操作过后一维会变得相同，直接上平衡树暴力模拟即可。
假如不考虑中途加点的话，我们可以简单地对每个点找到第一个操作到他的操作，分开考虑横向和纵向操作，那么能碰到这个点的操作长度在一个连续区间内，动态开点线段树即可。
为什么不支持中途加点呢？不难发现，中途加的点，在被操作一次之后不一定与之前被操作过的点满足单调性。
考虑线段树分治，对于每次询问，都在点出现的时刻到询问时刻这个区间所对应线段树上 \(O(\log Q)\) 个段插入该查询点，然后对线段树上每个节点都跑一遍完整过程即可。整体复杂度两个 \(\log\)。
感觉关键点就在于开头的那个性质，后面就是火箭毛毛虫大赛了。
code
const int M=2e6+5,Q=1e6+5;int n,m,q,c,qq;
struct node{int x,y,t;}ns[M];
struct cnode{int o,l;}cs[Q];
struct qnode{int x,y,t,be;}qs[Q];int cnt,rt[2];
int dat[Q*64],ls[Q*64],rs[Q*64];
void modify(int k,int v,int &x,int l=0,int r=1e9){if(!x)x=++cnt,ls[cnt]=rs[cnt]=0,dat[cnt]=inf;if(l==r)return chmin(dat[x],v),void();int m=l+r>>1;if(k<=m)modify(k,v,ls[x],l,m);else modify(k,v,rs[x],m+1,r);dat[x]=min(dat[ls[x]],dat[rs[x]]);
}
int query(int lq,int rq,int x,int l=0,int r=1e9){if(!x||lq>rq)return inf;if(lq<=l&&r<=rq)return dat[x];int m=l+r>>1,res=inf;if(lq<=m)chmin(res,query(lq,rq,ls[x],l,m));if(m<rq)chmin(res,query(lq,rq,rs[x],m+1,r));return res;
}auto rnd=mt19937_64(time(0));
struct FHQ{int ls[Q],rs[Q],lx[Q],ly[Q],pri[Q];void push(int x){if(~lx[x])qs[ls[x]].x=lx[ls[x]]=lx[x],qs[rs[x]].x=lx[rs[x]]=lx[x],lx[x]=-1;if(~ly[x])qs[ls[x]].y=ly[ls[x]]=ly[x],qs[rs[x]].y=ly[rs[x]]=ly[x],ly[x]=-1;}int merge(int a,int b){if(!a||!b)return a+b;if(pri[a]>pri[b]){push(a);rs[a]=merge(rs[a],b);return a;}else{push(b);ls[b]=merge(a,ls[b]);return b;}}void splitx(int x,int v,int &a,int &b){if(!x)return a=b=0,void();push(x);if(qs[x].x<=v)a=x,splitx(rs[x],v,rs[x],b);else b=x,splitx(ls[x],v,a,ls[x]);}void splity(int x,int v,int &a,int &b){if(!x)return a=b=0,void();push(x);if(qs[x].y>=v)a=x,splity(rs[x],v,rs[x],b);else b=x,splity(ls[x],v,a,ls[x]);}void upd(int x){if(!x)return;push(x);upd(ls[x]);upd(rs[x]);}void ins(int x,int &rt){int a,b,c;splitx(rt,qs[x].x,a,c);splity(a,qs[x].y,a,b);rt=merge(a,merge(x,merge(b,c)));}
}fhq;struct segment{vec<int> dat[Q<<2],tv[Q];void insert(int lq,int rq,int v,int x=1,int l=1,int r=c){if(lq>rq)return;if(lq<=l&&r<=rq)return dat[x].pub(v);int m=l+r>>1;if(lq<=m)insert(lq,rq,v,x<<1,l,m);if(m<rq)insert(lq,rq,v,x<<1|1,m+1,r);}void solve(int x=1,int l=1,int r=c){if(dat[x].size()){for(auto i:dat[x])fhq.ls[i]=fhq.rs[i]=0,fhq.lx[i]=fhq.ly[i]=-1,fhq.pri[i]=rnd();cnt=rt[0]=rt[1]=0;rep(i,l,r)modify(cs[i].l,i,rt[cs[i].o]);rep(i,l,r)tv[i].clear();for(auto i:dat[x]){qs[i].be=min(query(qs[i].y,n-qs[i].x,rt[0]),query(qs[i].x,n-qs[i].y,rt[1]));if(qs[i].be<=r)tv[qs[i].be].pub(i);}int rt=0;rep(i,l,r){if(cs[i].o){int a,b,c;fhq.splitx(rt,cs[i].l,a,c);fhq.splity(a,n-cs[i].l,a,b);qs[b].y=fhq.ly[b]=n-cs[i].l;rt=fhq.merge(fhq.merge(a,b),c);for(auto x:tv[i])qs[x].y=n-cs[i].l,fhq.ins(x,rt);}else{int a,b,c;fhq.splitx(rt,n-cs[i].l,a,c);fhq.splity(a,cs[i].l+1,a,b);qs[b].x=fhq.lx[b]=n-cs[i].l;rt=fhq.merge(fhq.merge(a,b),c);for(auto x:tv[i])qs[x].x=n-cs[i].l,fhq.ins(x,rt);}}fhq.upd(rt);}if(l<r){int m=l+r>>1;solve(x<<1,l,m);solve(x<<1|1,m+1,r);}}
}seg;inline void Main(){dat[0]=inf;cin>>n>>m>>q;rep(i,1,m)cin>>ns[i].x>>ns[i].y,ns[i].t=0;rep(i,1,q){int o;cin>>o;if(o==1){cin>>qs[++qq].x;qs[qq].t=c;}else if(o==2){cs[++c].o=0;cin>>cs[c].l;}else if(o==3){cs[++c].o=1;cin>>cs[c].l;}else{++m;cin>>ns[m].x>>ns[m].y;ns[m].t=c;}}q=qq;rep(i,1,q){int j=qs[i].x;qs[i].y=ns[j].y,qs[i].x=ns[j].x;seg.insert(ns[j].t+1,qs[i].t,i);}seg.solve();rep(i,1,q)cout<<qs[i].x<<" "<<qs[i].y<<"\n";
}