#include <bits/stdc++.h>
using namespace std;
using ll = long long; using pii = pair<ll,ll>;
const ll Qm = 15e5+5; const ll INF = 1e18;
const ll Nm = 100; //sparse segtree
mt19937 gen;
ll v2(ll x) {
return __builtin_ctz(x);
}
struct Node { //lazy sparse segtree
ll xl = -1,xr = -1;
map<ll,ll> mem;
Node(ll _xl, ll _xr) {
xl = _xl; xr = _xr;
}
void apmin(ll minv, ll ul, ll ur) { //apply to [ul,ur]: minv
for (auto A0: mem) {
if ((A0).first<=ur) {
mem[(A0).first]=max((A0).second,minv);
}
}
}
ll rdpt(ll x) { //read point
return mem[x];
}
void wpt(ll x, ll v) { //write a value of v to the point x
mem[x]=v;
}
ll gfloc(ll bmax, ll vmax) { //find any value among x<=bmax with value <=vmax or return -1
for (auto A0: mem) {
if ((A0).first<=bmax && (A0).second<=vmax) {
return (A0).first;
}
}
return -1;
}
};
Node* STroot;
ll l[Qm]; //treap left child (lower y)
ll r[Qm]; //treap right (higher y)
ll p[Qm]; //treap parent
ll ht[Qm]; //randomized binary search tree height
ll y[Qm]; //y-value (key)
ll x[Qm]; //x-value (store only for parents)
ll sz[Qm]; //treap size of subtree
ll cymin[Qm]; //child y-min of subtree
map<ll,ll> rootx; //x of root -> root value if exists
ll dsuf[Qm];
ll getf(ll x1) {
if (dsuf[x1]==x1) {
return x1;
}
return (dsuf[x1]=getf(dsuf[x1]));
}
void lft(ll rt) {
if (rt==-1) {
return;
}
sz[rt]=1;
cymin[rt]=y[rt];
if (l[rt]!=-1) {
p[l[rt]]=rt;
sz[rt]+=sz[l[rt]];
cymin[rt]=min(cymin[rt],cymin[l[rt]]);
}
if (r[rt]!=-1) {
p[r[rt]]=rt;
sz[rt]+=sz[r[rt]];
cymin[rt]=min(cymin[rt],cymin[r[rt]]);
}
}
void print(ll rt) {
return;
if (rt==-1) {
return;
}
//cout << "printing: rt="<<rt<<"\n";
//cout << "y="<<y[rt]<<"\n";
//cout << "l[rt]="<<l[rt]<<", r[rt]="<<r[rt]<<"\n";
print(l[rt]);
print(r[rt]);
}
pii cut(ll rt, ll v0) { //cut at root: y<=v0 go into left, y>v0 go into right
if (rt==-1) {
return {-1,-1};
}
if (y[rt]<=v0) {
pii pr = cut(r[rt],v0);
r[rt]=pr.first;
lft(rt);
lft(pr.first);
lft(pr.second);
p[rt]=-1;
if (pr.second!=-1) {
p[pr.second]=-1;
}
if (pr.second!=-1) {
assert(cymin[pr.second]>v0);
}
if (rt!=-1 && pr.second!=-1) {
assert(y[rt]<y[pr.second]);
}
return {rt,pr.second};
} else {
pii pr = cut(l[rt],v0);
l[rt]=pr.second;
lft(rt);
lft(pr.first);
lft(pr.second);
p[rt]=-1;
if (pr.first!=-1) {
p[pr.first]=-1;
}
if (cymin[rt]<=v0) {
cout << "print rt: \n";
print(rt);
cout << "print pr.first: \n";
print(pr.first);
exit(0);
}
assert(cymin[rt]>v0);
if (pr.first!=-1 && rt!=-1) {
assert(y[pr.first]<y[rt]);
}
return {pr.first,rt};
}
}
bool aset(ll rt, ll np) { //attempt to set, 1->valid, 0->invalid
if (rt==-1) {
return 0;
}
if (y[rt]==y[np]) {
dsuf[np]=rt;
return 1;
} else if (y[np]<y[rt]) {
if (l[rt]==-1) {
return 0;
}
return aset(l[rt],np);
} else {
if (r[rt]==-1) {
return 0;
}
return aset(r[rt],np);
}
}
ll fz(ll a, ll b) { //assume y[all terms in a] < y[all terms in b]
//cout << "fusing a,b="<<a<<","<<b<<"\n";
if (a==-1) {
return b;
}
if (b==-1) {
return a;
}
if (y[a]>=y[b]) {
//cout << "print a:\n";
print(a);
//cout << "print b:\n";
print(b);
exit(0);
}
assert(y[a]<y[b]);
lft(a);
lft(b);
if (ht[a]>=ht[b]) {
//cout << "fusing a above b\n";
r[a]=fz(r[a],b);
p[r[a]]=a;
lft(a);
lft(b);
return a;
} else {
//cout << "fusing b above a\n";
l[b]=fz(a,l[b]);
p[l[b]]=b;
lft(a);
lft(b);
return b;
}
}
ll upd(ll rt, ll np) { //root, new point
if (aset(rt,np)) { //attempt to set
return rt;
}
//cout << "print rt: \n";
print(rt);
//cout << "print np: \n";
print(np);
pii p0 = cut(rt,y[np]);
//cout << "p0: "<<p0.first<<","<<p0.second<<"\n";
//cout << "calling fz from upd\n";
ll rf = fz(fz(p0.first,np),p0.second);
x[rf]=x[rt];
return rf;
}
ll smin(ll rt, ll vt) { //set min to vt, return new root
//cout << "smin(rt="<<rt<<",vt="<<vt<<")\n";
pii p0 = cut(rt,vt);
//cout << "p0="<<p0.first<<","<<p0.second<<"\n";
if (p0.first==-1) {
return rt;
}
queue<ll> qpr;
qpr.push(p0.first);
while (!qpr.empty()) {
ll x0 = qpr.front(); qpr.pop();
//cout << "x0 in qpr: "<<x0<<"\n";
dsuf[x0]=p0.first;
if (l[x0]!=-1) {
qpr.push(l[x0]);
}
if (r[x0]!=-1) {
qpr.push(r[x0]);
}
}
l[p0.first]=-1;
r[p0.first]=-1;
sz[p0.first]=1;
y[p0.first]=vt;
p[p0.first]=-1;
cymin[p0.first]=vt;
//cout << "calling fz from smin\n";
ll rf = fz(p0.first,p0.second);
x[rf]=x[rt];
lft(rf);
return rf;
}
void pdn(ll x1) {
ll vpt = STroot->rdpt(x1);
//cout << "vpt="<<vpt<<"\n";
if (rootx.find(x1)==rootx.end()) {
return;
}
ll rt0 = rootx[x1];
lft(rt0);
ll rt1 = smin(rt0,vpt);
lft(rt1);
rootx[x1]=rt1;
x[rt1]=x1;
}
void put(ll x1, ll rtn) { //merge thing with root rtn into x1
//cout << "put rtn="<<rtn<<" into "<<x1<<"\n";
pdn(x1);
if (rtn==-1) {
return;
}
x[rtn]=x1;
if (rootx.find(x1)==rootx.end()) {
rootx[x1]=rtn;
x[rtn]=x1;
rootx[x1]=rtn;
STroot->wpt(x1,cymin[rtn]);
//cout << "setting x1,cymin="<<x1<<","<<cymin[rtn]<<"\n";
return;
}
ll rt0 = rootx[x1];
if (sz[rt0]>sz[rtn]) {
swap(rt0,rtn);
} //thus sz[rt0]<=sz[rtn]
queue<ll> q0;
vector<ll> v0;
q0.push(rt0);
while (!q0.empty()) {
ll ptt = q0.front(); q0.pop();
v0.push_back(ptt);
if (l[ptt]!=-1) {
q0.push(l[ptt]);
}
if (r[ptt]!=-1) {
q0.push(r[ptt]);
}
}
for (ll x0: v0) {
if (x0==-1) {
continue;
}
rtn = upd(rtn,x0);
}
rootx[x1]=rtn;
STroot->wpt(x1,cymin[rtn]);
x[rtn]=x1;
}
void doH(ll xmax, ll htf, ll x1prev=-1) {
//cout << "doH: xmax="<<xmax<<", htf="<<htf<<"\n";
ll x1 = STroot->gfloc(xmax-1,htf);
//cout << "x1="<<x1<<"\n";
if (x1==-1) {
return;
}
//assert(x1!=x1prev);
pdn(x1);
ll r1 = rootx[x1];
lft(r1);
pii p0 = cut(r1,htf);
//cout << "p0 upon cutting: "<<p0.first<<","<<p0.second<<"\n";
if (p0.first==-1) {
return;
}
put(xmax,p0.first);
if (p0.second!=-1) {
//cout << "write ymin: "<<cymin[p0.second]<<"\n";
STroot->wpt(x1,cymin[p0.second]);
//assert(cymin[p0.second]>htf);
x[p0.second]=x1;
rootx[x1]=p0.second;
} else {
STroot->wpt(x1,INF);
rootx.erase(rootx.find(x1));
}
doH(xmax,htf,x1);
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(0);
ll N,M,Q; cin >> N >> M >> Q;
gen = mt19937((long long) new char);
STroot = new Node(0,Nm-1);
for (ll q=0;q<Qm;q++) {
dsuf[q]=q;
}
for (ll m=0;m<M;m++) {
ll x1,y1; cin >> x1 >> y1;
l[m]=-1;
r[m]=-1;
p[m]=-1;
ht[m]=gen();
y[m]=y1;
x[m]=x1;
sz[m]=1;
cymin[m]=y1;
put(x1,m);
}
ll ndust = M;
for (ll q=0;q<Q;q++) {
ll t1; cin >> t1;
if (t1==1) {
ll pc; cin >> pc; pc--;
pc = getf(pc);
//cout << "pc="<<pc<<"\n";
ll rt = pc;
while (p[rt]!=-1) {
assert(l[p[rt]]==rt || r[p[rt]]==rt);
assert(ht[p[rt]]>=ht[rt]);
assert(p[rt]!=rt);
rt = p[rt];
}
ll xc = x[rt];
pdn(xc);
pc = getf(pc);
cout << xc << " " << y[pc] <<"\n";
} else if (t1==2) {
ll wc; cin >> wc;
doH(N-wc,wc);
} else if (t1==3) {
ll wc; cin >> wc;
STroot->apmin(N-wc,0,wc);
} else {
ll x1,y1; cin >> x1 >> y1;
ll m = ndust;
l[m]=-1;
r[m]=-1;
p[m]=-1;
ht[m]=gen();
y[m]=y1;
x[m]=x1;
sz[m]=1;
cymin[m]=y1;
put(x1,m);
ndust++;
}
}
}
