#include <bits/stdc++.h> #define ll long long #define pii pair<int,int> using namespace std; const int MAX=2e6+5; int N,M,Q; int rt[MAX]; struct SOL{ int s,e,m,d; SOL *l=0,*r=0; map<pii,vector<int>> X,Y; unordered_map<int,int> xpar,ypar,xv,yv; SOL(int s,int e):s(s),e(e),m((s+e)>>1),d(e-s+1){} void cc(){ if (d>1){ if (!l) l=new SOL(s,m-1); if (!r) r=new SOL(m+1,e); } } void add(int i,int x,int y){ cc(); if (d>1){ if (x>m) return r->add(i,x,y); if (y>N-m) return l->add(i,x,y); } rt[i]=m; xpar[i]=ypar[i]=i; xv[i]=x,yv[i]=y; X[{x,i}]={i}; Y[{y,i}]={i}; } void updx(int x){ cc(); if (x>m){ while (Y.size()&&Y.begin()->first.first<=N-x){ auto st=Y.begin()->second; auto par=Y.begin()->first.second; Y.erase(Y.begin()); for (auto i:st){ if (rt[i]!=m) continue; r->add(i,x,yv[par]); xpar.erase(i),ypar.erase(i); } yv.erase(par); } if (d>1) r->updx(x); }else{ int par=-1; vector<int> rst; vector<vector<int>> V; while (X.size()&&X.begin()->first.first<=x){ auto st=X.begin()->second; auto p=X.begin()->first.second; X.erase(X.begin()); if (st.size()>rst.size()) swap(st,rst),par=p; V.push_back(st); } while (V.size()){ auto st=V.back(); V.pop_back(); for (auto i:st) if (rt[i]==m) rst.push_back(i),xpar[i]=par; } if (par!=-1){ xv[par]=x; X[{x,par}]=rst; } if (d>1) l->updx(x); } } void updy(int y){ cc(); if (y>N-m){ while (X.size()&&X.begin()->first.first<=N-y){ auto st=X.begin()->second; auto par=X.begin()->first.second; X.erase(X.begin()); for (auto i:st){ if (rt[i]!=m) continue; l->add(i,xv[par],y); xpar.erase(i),ypar.erase(i); } xv.erase(par); } if (d>1) l->updy(y); }else{ int par=-1; vector<int> rst; vector<vector<int>> V; while (Y.size()&&Y.begin()->first.first<=y){ auto st=Y.begin()->second; auto p=Y.begin()->first.second; Y.erase(Y.begin()); if (st.size()>rst.size()) swap(st,rst),par=p; V.push_back(st); } while (V.size()){ auto st=V.back(); V.pop_back(); for (auto i:st) if (rt[i]==m) rst.push_back(i),ypar[i]=par; } if (par!=-1){ yv[par]=y; Y[{y,par}]=rst; } if (d>1) r->updy(y); } } pii qry(int i){ if (rt[i]>m) return r->qry(i); if (rt[i]<m) return l->qry(i); return {xv[xpar[i]],yv[ypar[i]]}; } }; int main(){ ios::sync_with_stdio(0);cin.tie(0); cin>>N>>M>>Q; auto sol=new SOL(0,N); for (int i=0;i<M;i++){ int x,y;cin>>x>>y; sol->add(i,x,y); } int c=M; while (Q--){ int t; cin>>t; if (t==1){ int i;cin>>i;i--; auto ans=sol->qry(i); cout<<ans.first<<' '<<ans.second<<'\n'; }else if (t==2){ int x;cin>>x; sol->updx(N-x); }else if (t==3){ int y;cin>>y; sol->updy(N-y); }else{ int x,y;cin>>x>>y; sol->add(c++,x,y); } } }