#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef long double ld;
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds;
vector<ii> pt;
struct query
{
int ty,val,id;
query(int _ty=0,int _val=0,int _id=0): ty(_ty),val(_val),id(_id){}
};
int par[3333333];
struct DSU
{
vi val;
vector<vi> pset;
void init()
{
val.clear(); pset.clear();
}
int add(int v, int id) //v = coordinate, id = id of point
{
int newid = val.size();
val.pb(v); pset.pb({});
if(id>=0)
{
par[id]=newid; //change the parent x or y of the point
pset[newid].pb(id);
}
return newid;
}
int merge(int x, int y)
{
if(x==y) return x;
if(pset[x].size()<pset[y].size()) swap(x,y);
val[x]=max(val[x],val[y]);
for(int z:pset[y])
{
par[z]=x; pset[x].pb(z);
}
return x;
}
};
vector<query> queries;
ii ans[1111111];
int n,m,q;
DSU dsu;
ii getcoord(int id) //get coordinates of the point id
{
//cerr<<id<<' '<<dsu.val.size()<<' '<<par[id*2]<<' '<<par[id*2+1]<<'\n';
return {dsu.val[par[id*2]],dsu.val[par[id*2+1]]};
}
bool pushed[2222222];
void solve(int x, int y, vector<query> Q)
{
if(Q.empty()) return ;
/*
cerr<<"SOLVE "<<x<<' '<<y<<'\n';
cerr<<"QUERIES: \n";
for(query qq:Q)
{
cerr<<qq.ty<<' '<<qq.val<<' '<<qq.id<<'\n';
}
*/
if(x+y==n)
{
for(auto qry:Q)
{
if(qry.ty==1) ans[qry.id]=pt[qry.val];
}
return ;
}
dsu.init();
int X = x+(n-x-y)/2+1; int Y = n+1-X; //X+Y=N+1
//cerr<<X<<' '<<Y<<'\n';
vector<query> up,right;
priority_queue<ii,vector<ii>,greater<ii> > xcoord,ycoord;
for(auto qry:Q)
{
//cerr<<qry.ty<<' '<<qry.val<<' '<<qry.id<<' '<<pt.size()<<'\n';
//cerr<<dsu.val.size()<<'\n';
if(qry.ty==1)
{
int ptid = qry.val;
if(pt[ptid].fi>=X) right.pb(qry);
else if(pt[ptid].se>=Y) up.pb(qry);
else
{
//cerr<<"QUERY OF ID "<<qry.id<<" HAS BEEN ANSWERED\n";
ans[qry.id]=getcoord(ptid);
}
}
else if(qry.ty==2)
{
//horizontal motion
int L = qry.val;
if(L>=Y) //everything in range with x < n-l gets swept to the right. note that n-L<=n-Y is still in the range, so our points don't get pushed outside the box yet
{
int newx = n-L;
int curid = dsu.add(newx,-1);
while(!xcoord.empty())
{
int tpx = xcoord.top().fi;
if(tpx>=n-L) break;
curid=dsu.merge(curid,xcoord.top().se);
xcoord.pop();
}
xcoord.push({newx,curid});
up.pb(qry);
}
else
{
//ycoord<=L suffer
while(!ycoord.empty())
{
int tpy = ycoord.top().fi;
if(tpy>L) break;
int dsuid = ycoord.top().se; ycoord.pop();
//for all the points with this coordinate
for(int p:dsu.pset[dsuid]) //a point gets traversed at most log (M+Q) times here and under log N recursive calls
{
p/=2;
if(!pushed[p])
{
pt[p] = getcoord(p);
pt[p].fi = n-L;
right.pb(query(4,p,-1)); //new point position later
pushed[p]=1;
}
}
}
right.pb(qry);
}
}
else if(qry.ty==3)
{
int L = qry.val;
if(L>=X)
{
int newy = n-L;
int curid = dsu.add(newy,-1);
while(!ycoord.empty())
{
int tpy = ycoord.top().fi;
if(tpy>=n-L) break;
curid=dsu.merge(curid,ycoord.top().se);
ycoord.pop();
}
ycoord.push({newy,curid});
right.pb(qry);
}
else
{
while(!xcoord.empty())
{
int tpx = xcoord.top().fi;
//cerr<<tpx<<'\n';
if(tpx>L) break;
int dsuid = xcoord.top().se; xcoord.pop();
//for all the points with this coordinate
for(int p:dsu.pset[dsuid]) //a point gets traversed at most log (M+Q) times here and under log N recursive calls
{
p/=2;
if(!pushed[p])
{
pt[p] = getcoord(p);
pt[p].se = n-L;
//cerr<<pt[p].fi<<' '<<pt[p].se<<'\n';
up.pb(query(4,p,-1)); //new point position later
pushed[p]=1;
}
}
}
up.pb(qry);
}
}
else
{
int ptid = qry.val;
pushed[ptid]=0; //reset point
int x = pt[ptid].fi; int y = pt[ptid].se;
if(y>=Y){pushed[ptid]=1; up.pb(qry);}
else if(x>=X){pushed[ptid]=1; right.pb(qry);}
//the point belongs here
else
{
int xid = dsu.add(x,2*ptid);
int yid = dsu.add(y,2*ptid+1);
xcoord.push({x,xid});
ycoord.push({y,yid});
}
}
}
solve(X,y,right); solve(x,Y,up);
}
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0);
cin>>n>>m>>q;
vi T;
for(int i=0;i<m;i++)
{
int x,y; cin>>x>>y;
pt.pb({x,y}); T.pb(0);
queries.pb(query(4,i,-1));
}
for(int i=0;i<q;i++)
{
int t; cin>>t;
if(t==4)
{
int x,y; cin>>x>>y;
queries.pb(query(4,pt.size(),-1));
pt.pb({x,y});
continue;
}
int val; cin>>val;
if(t==1) val--;
queries.pb(query(t,val,i));
}
for(int i=0;i<q;i++) ans[i]={-1,-1};
solve(0,0,queries);
for(int i=0;i<q;i++)
{
if(ans[i].fi>=0) cout<<ans[i].fi<<' '<<ans[i].se<<'\n';
}
}
