#define DEBUG 0
#include <bits/stdc++.h>
using namespace std;
#if DEBUG
// basic debugging macros
int __i__,__j__;
#define printLine(l) for(__i__=0;__i__<l;__i__++){cout<<"-";}cout<<endl
#define printLine2(l,c) for(__i__=0;__i__<l;__i__++){cout<<c;}cout<<endl
#define printVar(n) cout<<#n<<": "<<n<<endl
#define printArr(a,l) cout<<#a<<": ";for(__i__=0;__i__<l;__i__++){cout<<a[__i__]<<" ";}cout<<endl
#define print2dArr(a,r,c) cout<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<a[__i__][__j__]<<" ";}cout<<endl;}
#define print2dArr2(a,r,c,l) cout<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<setw(l)<<setfill(' ')<<a[__i__][__j__]<<" ";}cout<<endl;}
// advanced debugging class
// debug 1,2,'A',"test";
class _Debug {
public:
template<typename T>
_Debug& operator,(T val) {
cout << val << endl;
return *this;
}
};
#define debug _Debug(),
#else
#define printLine(l)
#define printLine2(l,c)
#define printVar(n)
#define printArr(a,l)
#define print2dArr(a,r,c)
#define print2dArr2(a,r,c,l)
#define debug
#endif
// define
#define MAX_VAL 999999999
#define MAX_VAL_2 999999999999999999LL
#define EPS 1e-6
#define mp make_pair
#define pb push_back
// typedef
typedef unsigned int UI;
typedef long long int LLI;
typedef unsigned long long int ULLI;
typedef unsigned short int US;
typedef pair<int,int> pii;
typedef pair<LLI,LLI> plli;
typedef vector<int> vi;
typedef vector<LLI> vlli;
typedef vector<pii> vpii;
typedef vector<plli> vplli;
// ---------- END OF TEMPLATE ----------
template<typename T1,typename T2>
ostream& operator<<(ostream& output,const pair<T1,T2> &p) {
output << "(" << p.first << "," << p.second << ")";
return output;
}
template<typename T>
ostream& operator<<(ostream& output,const vector<T> &v) {
unsigned int i;
bool f = 1;
for (i = 0; i < v.size(); i++) {
if (!f) output << " ";
output << v[i];
f = 0;
}
return output;
}
template<typename T>
ostream& operator<<(ostream& output,const list<T> &l) {
typename list<T>::const_iterator it;
bool f = 1;
for (it = l.begin(); it != l.end(); it++) {
if (!f) output << " ";
output << *it;
f = 0;
}
return output;
}
template<typename T1,typename T2>
ostream& operator<<(ostream& output,const map<T1,T2> &m) {
typename map<T1,T2>::const_iterator it;
bool f = 1;
for (it = m.begin(); it != m.end(); it++) {
if (!f) output << " ";
output << "(" << it->first << " -> " << it->second << ")";
f = 0;
}
return output;
}
template<typename T>
ostream& operator<<(ostream& output,const set<T> &s) {
typename set<T>::const_iterator it;
bool f = 1;
for (it = s.begin(); it != s.end(); it++) {
if (!f) output << " ";
output << *it;
f = 0;
}
return output;
}
int X[1500000],Y[1500000];
map<int,pii> MM;
struct func { int l,r,d,u,x,y; };
vector<func> f;
int insert(map<pii,pii> &M,int l,int r,pii p) {
//debug "here",l,r,p;
//debug M;
auto it = M.upper_bound(mp(l,2e9));
if (it != M.begin()) {
it--;
pair<pii,pii> q = *it;
if ((q.first.first <= l) && (l <= q.first.second)) {
M.erase(it);
if (l-1 >= q.first.first) M[mp(q.first.first,l-1)] = q.second;
M[mp(l,q.first.second)] = q.second;
}
}
//debug M;
it = M.upper_bound(mp(r,2e9));
if (it != M.begin()) {
it--;
pair<pii,pii> q = *it;
if ((q.first.first <= r) && (r <= q.first.second)) {
M.erase(it);
if (r+1 <= q.first.second) M[mp(r+1,q.first.second)] = q.second;
M[mp(q.first.first,r)] = q.second;
}
}
//debug M;
it = M.lower_bound(mp(l,0));
while ((it != M.end()) && (it->first.second <= r)) assert(it->first.second >= l),it = M.erase(it);
M[mp(l,r)] = p;
//debug M;
return 0;
}
struct node {
node *l,*r;
map<pii,pii> M;
int update(int s,int e,int as,int ae,int d,int u,pii p) {
//cout<<as<<","<<ae<<","<<d<<","<<u<<": "<<p.first<<","<<p.second<<endl;
//cout<<s<<","<<e<<endl;
if ((s >= as) && (e <= ae)) {
insert(M,d,u,p);
return 0;
}
int mid = (s+e) / 2;
if (as <= mid) {
if (l == NULL) l = new node(),l->l = l->r = NULL;
l->update(s,mid,as,ae,d,u,p);
}
if (ae >= mid+1) {
if (r == NULL) r = new node(),r->l = r->r = NULL;
r->update(mid+1,e,as,ae,d,u,p);
}
return 0;
}
pii query(int s,int e,int q,int qy) {
int mid = (s+e) / 2;
pii ans = mp(-1,-1);
auto it = M.upper_bound(mp(qy,2e9));
if (it != M.begin()) {
it--;
if ((it->first.first <= qy) && (qy <= it->first.second)) ans = it->second;
}
if (q <= mid) {
if (l != NULL) {
pii ans2 = l->query(s,mid,q,qy);
if (ans.first+ans.second < ans2.first+ans2.second) ans = ans2;
}
}
else {
if (r != NULL) {
pii ans2 = r->query(mid+1,e,q,qy);
if (ans.first+ans.second < ans2.first+ans2.second) ans = ans2;
}
}
return ans;
}
};
node *root;
int update(int x,int t,int N) {
auto it = MM.lower_bound(x);
if (it->first == x) return 0;
auto it2 = it;
it2--;
if (t == 1) {
f.pb((func){it2->first-it2->second.first,x-1,N-it->first,N-x-1,x,-1});
f.pb((func){it2->first-it2->second.first,x-1,N-it->first-it->second.second,N-it->first,x,N-it->first});
MM[x] = mp(it2->second.first+x-it2->first,0);
}
else {
f.pb((func){it2->first,x-1,N-it->first-it->second.second,N-x-1,-1,N-x});
f.pb((func){it2->first-it2->second.first,it2->first,N-it->first-it->second.second,N-x-1,it2->first,N-x});
MM[x] = mp(0,it->second.second+it->first-x);
}
func a = f[f.size()-2],b = f.back();
swap(a,b);
assert((a.l >= 0) && (a.d >= 0) && (a.r <= N+5) && (a.u <= N+5));
if ((a.l <= a.r) && (a.d <= a.u)) root->update(0,N+5,a.l,a.r,a.d,a.u,mp(a.x,a.y));
swap(a,b);assert((a.l >= 0) && (a.d >= 0) && (a.r <= N+5) && (a.u <= N+5));
if ((a.l <= a.r) && (a.d <= a.u)) root->update(0,N+5,a.l,a.r,a.d,a.u,mp(a.x,a.y));
return 0;
}
vpii ops;
int t[1000000],p[1000000],l[1000000],a[1000000],b[1000000];
int tree[1 << 22],lazy[1 << 22];
int prop(int s,int e,int i) {
tree[i] = max(tree[i],lazy[i]);
if (s != e) {
lazy[2*i+1] = max(lazy[2*i+1],lazy[i]);
lazy[2*i+2] = max(lazy[2*i+2],lazy[i]);
}
lazy[i] = 0;
return 0;
}
int update(int s,int e,int as,int ae,int i,int num,int t) {
prop(s,e,i);
if ((s > ae) || (e < as)) return 0;
else if ((s >= as) && (e <= ae)) {
lazy[i] = num;
if (t) tree[i] = num;
prop(s,e,i);
return 0;
}
int mid = (s+e) / 2;
update(s,mid,as,ae,2*i+1,num,t),update(mid+1,e,as,ae,2*i+2,num,t);
tree[i] = max(tree[2*i+1],tree[2*i+2]);
return 0;
}
int query(int s,int e,int qs,int qe,int i) {
prop(s,e,i);
if ((s > qe) || (e < qs)) return 0;
else if ((s >= qs) && (e <= qe)) return tree[i];
int mid = (s+e) / 2;
return max(query(s,mid,qs,qe,2*i+1),query(mid+1,e,qs,qe,2*i+2));
}
int main() {
int i;
int N,M,Q;
int T,P,L,A,B,sub2 = 1;
scanf("%d %d %d",&N,&M,&Q);
for (i = 0; i < M; i++) scanf("%d %d",&X[i],&Y[i]);
for (i = 0; i < Q; i++) {
scanf("%d",&t[i]);
if (t[i] == 1) scanf("%d",&p[i]);
else if (t[i] <= 3) scanf("%d",&l[i]);
else scanf("%d %d",&a[i],&b[i]);
if (t[i] == 3) sub2 = 0;
}
if (sub2) {
vpii possy;
int c = M;
for (i = 0; i < M; i++) possy.pb(mp(Y[i],i));
for (i = 0; i < Q; i++) {
if (t[i] == 4) possy.pb(mp(b[i],c++));
}
sort(possy.begin(),possy.end());
for (i = 0; i < M; i++) {
int x = lower_bound(possy.begin(),possy.end(),mp(Y[i],i))-possy.begin();
update(0,c-1,x,x,0,X[i],1);
}
int c2 = M;
for (i = 0; i < Q; i++) {
if (t[i] == 1) {
int x = lower_bound(possy.begin(),possy.end(),mp(Y[p[i]-1],p[i]-1))-possy.begin();
printf("%d %d\n",query(0,c-1,x,x,0),Y[p[i]-1]);
}
else if (t[i] == 2) {
int x = upper_bound(possy.begin(),possy.end(),mp(l[i],(int) 2e9))-possy.begin()-1;
update(0,c-1,0,x,0,N-l[i],0);
}
else {
X[c2] = a[i],Y[c2++] = b[i];
int x = lower_bound(possy.begin(),possy.end(),mp(Y[c2-1],c2-1))-possy.begin();
update(0,c-1,x,x,0,X[c2-1],1);
}
}
return 0;
}
MM[0] = MM[N+1] = mp(0,0);
root = new node;
root->l = root->r = NULL;
for (i = 0; i < Q; i++) {
T = t[i];
if (T == 1) {
P = p[i],P--;
pii ans = root->query(0,N+6,X[P],Y[P]);
int xx = X[P],yy = Y[P];
if (ans.first != -1) xx = ans.first;
if (ans.second != -1) yy = ans.second;
printf("%d %d\n",xx,yy);/*
pii p = mp(xx,yy);
int j;
for (j = f.size()-1; j >= 0; j--) {
if ((X[P] >= f[j].l) && (X[P] <= f[j].r) && (Y[P] >= f[j].d) && (Y[P] <= f[j].u)) {
int xx = X[P],yy = Y[P];
if (f[j].x != -1) xx = f[j].x;
if (f[j].y != -1) yy = f[j].y;
printf("o:%d %d\n",xx,yy);
assert(p == mp(xx,yy));
break;
}
}
if (j < 0) printf("o:%d %d\n",X[P],Y[P]),assert(p == mp(X[P],Y[P]));*/
}
else if (T == 2) {
L = l[i];
ops.pb(mp(T,L));
update(N-L,1,N+1);
}
else if (T == 3) {
L = l[i];
ops.pb(mp(T,L));
update(L+1,2,N+1);
}
else {
A = a[i],B = b[i];
break;
}
}
if (i < Q) {
int pp = i;
for (i = 0; i < ops.size(); i++) {
int j;
for (j = 0; j < M; j++) {
if (ops[i].first == 2) {
if ((Y[j] <= ops[i].second) && (X[j] < N-ops[i].second)) X[j] = N-ops[i].second;
}
else {
if ((X[j] <= ops[i].second) && (Y[j] < N-ops[i].second)) Y[j] = N-ops[i].second;
}
}
}
X[M++] = A,Y[M-1] = B;
for (i = pp+1; i < Q; i++) {
T = t[i];
if (T == 1) {
P = p[i],P--;
printf("%d %d\n",X[P],Y[P]);
}
else if (T == 2) {
L = l[i];
int j;
for (j = 0; j < M; j++) {
if ((Y[j] <= L) && (X[j] < N-L)) X[j] = N-L;
}
}
else if (T == 3) {
L = l[i];
int j;
for (j = 0; j < M; j++) {
if ((X[j] <= L) && (Y[j] < N-L)) Y[j] = N-L;
}
}
else {
A = a[i],B = b[i];
X[M++] = A,Y[M-1] = B;
}
}
}
return 0;
}
