#include <bits/stdc++.h> #define ll long long #define pii pair<int,int> #define pr(a,b) ((a)*MAX+(b)) #define q(a) pr(m,a) using namespace std; const ll MAX=2e6+5; int N,M,Q; int rt[MAX]; unordered_map<ll,int> xpar,ypar,xv,yv; struct SOL{ int s,e,m,d; SOL *l=0,*r=0; priority_queue<pair<pii,vector<int>>,vector<pair<pii,vector<int>>>,greater<>> X,Y; 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[q(i)]=ypar[q(i)]=i; xv[q(i)]=x,yv[q(i)]=y; X.push({{x,i},{i}}); Y.push({{y,i},{i}}); } void updx(int x){ cc(); if (x>m){ while (Y.size()&&Y.top().first.first<=N-x){ auto st=Y.top().second; auto par=Y.top().first.second; Y.pop(); for (auto i:st){ if (rt[i]!=m) continue; r->add(i,x,yv[q(par)]); xpar.erase(q(i)),ypar.erase(q(i)); } yv.erase(q(par)); } if (d>1) r->updx(x); }else{ int par=-1; vector<int> rst; vector<vector<int>> V; while (X.size()&&X.top().first.first<=x){ auto st=X.top().second; auto p=X.top().first.second; X.pop(); 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[q(i)]=par; } if (par!=-1){ xv[q(par)]=x; X.push({{x,par},rst}); } if (d>1) l->updx(x); } } void updy(int y){ cc(); if (y>N-m){ while (X.size()&&X.top().first.first<=N-y){ auto st=X.top().second; auto par=X.top().first.second; X.pop(); for (auto i:st){ if (rt[i]!=m) continue; l->add(i,xv[q(par)],y); xpar.erase(q(i)),ypar.erase(q(i)); } xv.erase(q(par)); } if (d>1) l->updy(y); }else{ int par=-1; vector<int> rst; vector<vector<int>> V; while (Y.size()&&Y.top().first.first<=y){ auto st=Y.top().second; auto p=Y.top().first.second; Y.pop(); 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[q(i)]=par; } if (par!=-1){ yv[q(par)]=y; Y.push({{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[q(xpar[q(i)])],yv[q(ypar[q(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); } } }