#include <bits/stdc++.h>
using namespace std;
using ii = pair<int, int>;
const int inf = 1e9 + 7;
#define X first
#define Y second
mt19937 rng(chrono::steady_clock().now().time_since_epoch().count());
uniform_int_distribution<int> uid(INT_MIN, INT_MAX);
void readint(int &a) {
char c;
a = 0;
do {
c = getchar_unlocked();
} while(c < '0' || c > '9');
do {
a = a * 10 + c - '0';
c = getchar_unlocked();
} while(c >= '0' && c <= '9');
}
int rand() {
return uid(rng);
}
struct STNode {
STNode *l, *r;
ii v;
STNode(ii v = {inf, inf}) {
this->v = v;
l = r = nullptr;
}
void upd() {
v = {inf, inf};
if(l != nullptr)
v = min(v, l->v);
if(r != nullptr)
v = min(v, r->v);
}
};
struct SegmentTree {
int lv;
STNode *root;
SegmentTree(int n) {
root = new STNode();
lv = 2;
while(lv < n + 2)
lv *= 2;
}
void del_nodes(STNode *n) {
if(n == nullptr)
return ;
del_nodes(n->l);
del_nodes(n->r);
delete n;
}
~SegmentTree() {
del_nodes(root);
}
void insert(STNode *&n, int l, int r, int w, int v) {
//~ cout << "a" << endl;
if(n == nullptr)
n = new STNode();
if(l == r) {
n->v = {v, l};
return ;
}
if(w <= (l + r) / 2)
insert(n->l, l, (l + r) / 2, w, v);
else
insert(n->r, (l + r) / 2 + 1, r, w, v);
n->upd();
}
ii query(STNode *&n, int l, int r, int a, int b) {
if(n == nullptr || r < a || l > b || l > r)
return {inf, inf};
if(a <= l && r <= b)
return n->v;
return min(query(n->l, l, (l + r) / 2, a, b),
query(n->r, (l + r) / 2 + 1, r, a, b));
}
void insert(int w, int v) {
insert(root, 0, lv - 1, w, v);
}
ii query(int a, int b) {
return query(root, 0, lv - 1, a, b);
}
};
struct TreapNode {
TreapNode *l, *r, *p;
int x, y, q, lazyx, lazyy;
TreapNode(int _x, int _y) {
x = _x;
y = _y;
q = rand();
l = r = p = nullptr;
lazyx = 0;
lazyy = 0;
}
TreapNode* attach(TreapNode *ll, TreapNode *rr) {
l = ll;
r = rr;
if(l != nullptr)
l->p = this;
if(r != nullptr)
r->p = this;
return this;
}
void push() {
if(!lazyx && !lazyy)
return ;
x = max(x, lazyx);
y = max(y, lazyy);
if(l != nullptr) {
l->lazyx = max(l->lazyx, lazyx);
l->lazyy = max(l->lazyy, lazyy);
}
if(r != nullptr) {
r->lazyx = max(r->lazyx, lazyx);
r->lazyy = max(r->lazyy, lazyy);
}
lazyx = 0;
lazyy = 0;
}
void print() {
push();
cout << "[";
if(l != nullptr)
l->print();
cout << "]";
cout << "(" << x << ", " << y << ")[";
if(r != nullptr)
r->print();
cout << "]";
}
};
struct Treap {
TreapNode *root;
map<int, TreapNode*> M;
int total;
Treap() {
root = new TreapNode(0, 0);
total = 1;
}
~Treap() {
for(auto p : M)
delete p.Y;
}
TreapNode* merge(TreapNode *a, TreapNode *b) {
if(a == nullptr)
return b;
if(b == nullptr)
return a;
a->push();
b->push();
if(a->q < b->q)
return a->attach(a->l, merge(a->r, b));
else
return b->attach(merge(a, b->l), b->r);
}
bool comp(int x1, int y1, int x2, int y2) {
return (x1 < x2 || y1 > y2);
}
pair<TreapNode*, TreapNode*> split(TreapNode *n, int x, int y) {
if(n == nullptr)
return {nullptr, nullptr};
n->push();
if(comp(x, y, n->x, n->y)) {
TreapNode *m = n->l;
n->attach(nullptr, n->r);
auto p = split(m, x, y);
return {p.X, n->attach(p.Y, n->r)};
} else {
TreapNode *m = n->r;
n->attach(n->l, nullptr);
auto p = split(m, x, y);
return {n->attach(n->l, p.X), p.Y};
}
}
void insert(int i, int x, int y) {
TreapNode *n = new TreapNode(x, y);
M[i] = n;
auto p = split(root, x, y);
root = merge(merge(p.X, n), p.Y);
total++;
}
// dla x' <= x
void maxy(int x, int v) {
auto p = split(root, x, -1);
if(p.X != nullptr)
p.X->lazyy = max(p.X->lazyy, v);
root = merge(p.X, p.Y);
}
// dla y' <= y
void maxx(int y, int v) {
auto p = split(root, inf, y+1);
//~ cout << "maxx split" << endl;
//~ if(p.X != nullptr) p.X->print(); cout << endl;
//~ if(p.Y != nullptr) p.Y->print(); cout << endl;
if(p.Y != nullptr)
p.Y->lazyx = max(p.Y->lazyx, v);
root = merge(p.X, p.Y);
}
void process_lazy_up(TreapNode *n) {
if(n == nullptr)
return ;
process_lazy_up(n->p);
n->push();
}
ii query(int i) {
TreapNode *n = M[i];
process_lazy_up(n);
return {n->x, n->y};
}
void print() {
root->print();
cerr << endl;
}
void push(TreapNode *n) {
if(n == nullptr)
return ;
n->push();
push(n->l);
push(n->r);
}
vector<pair<int, ii> > pushall() {
push(root);
vector<pair<int, ii> > res;
res.reserve(total);
for(auto p : M)
res.push_back({p.X, {p.Y->x, p.Y->y}});
return res;
}
};
bool on_treap[2000007];
int nxt[2000007];
bool comp(pair<int, ii> &a, pair<int, ii> &b) {
return a.Y < b.Y;
}
struct Points {
// inicjalizujemy punktami, ktore sie nie zmieniaja
// wrzucamy wszystkie na drzewo i mape wektorow
// treap pusty
// przy kazdym zapytaniu najpierw aktualizujemy treapa, potem przerzucamy na niego punkty
int n, m;
Treap *T;
SegmentTree *ST;
map<int, ii> initial_cor;
map<int, int> M;
Points(vector<pair<int, ii> > &P, int n) {
this->n = n;
T = new Treap();
ST = new SegmentTree(inf);
sort(P.begin(), P.end(), comp);
for(int i = 0 ; i < P.size() ; i++) {
initial_cor[P[i].X] = P[i].Y;
if(i + 1 < P.size() && P[i + 1].Y.X == P[i].Y.X)
nxt[P[i].X] = P[i + 1].X;
else
nxt[P[i].X] = -1;
if(i == 0 || P[i - 1].Y.X < P[i].Y.X) {
ST->insert(P[i].Y.X, P[i].Y.Y);
M[P[i].Y.X] = P[i].X;
}
}
m = P.size();
}
~Points() {
for(auto p : initial_cor)
on_treap[p.X] = 0;
delete T;
delete ST;
}
ii query(int i) {
if(on_treap[i])
return T->query(i);
else
return initial_cor[i];
}
void sweep_horizontally(int s) {
T->maxx(s, n - s);
ii p;
while((p = ST->query(0, n - s)).X <= s) {
int x = p.Y;
T->insert(M[x], n - s, initial_cor[M[x]].Y);
on_treap[M[x]] = 1;
M[x] = nxt[M[x]];
int v = inf;
if(M[x] != -1)
v = initial_cor[M[x]].Y;
ST->insert(x, v);
}
}
void sweep_vertically(int s) {
T->maxy(s, n - s);
ii p;
while((p = ST->query(0, s)).X <= n - s) {
int x = p.Y;
T->insert(M[x], x, n - s);
on_treap[M[x]] = 1;
M[x] = nxt[M[x]];
int v = inf;
if(M[x] != -1)
v = initial_cor[M[x]].Y;
ST->insert(x, v);
}
}
int size() {
return m;
}
vector<pair<int, ii> > get_all_points() {
vector<pair<int, ii>> res = T->pushall();
for(auto p : initial_cor) {
if(!on_treap[p.X])
res.push_back({p.X, p.Y});
}
return res;
}
};
struct MasterPoints {
int n;
Points *I;
vector<Points*> P;
map<int, Points*> M;
MasterPoints(vector<pair<int, ii> > &P, int n) {
this->n = n;
I = new Points(P, n);
for(auto p : P)
M[p.X] = I;
}
ii query(int i) {
return M[i]->query(i);
}
void sweep_horizontally(int s) {
I->sweep_horizontally(s);
for(auto p : P)
p->sweep_horizontally(s);
}
void sweep_vertically(int s) {
I->sweep_vertically(s);
for(auto p : P)
p->sweep_vertically(s);
}
void add_point(int i, int x, int y) {
vector<pair<int, ii> > PPP;
PPP.push_back({i, {x, y}});
while(P.size() && P.back()->size() == PPP.size()) {
auto P1 = P.back()->get_all_points();
delete P.back();
P.pop_back();
for(auto p : P1)
PPP.push_back(p);
}
P.push_back(new Points(PPP, n));
for(auto p : PPP)
M[p.X] = P.back();
//~ cerr << P.size() << endl;
}
};
int n, m, q;
MasterPoints *PP;
int main() {
//~ scanf("%d%d%d", &n, &m, &q);
readint(n);
readint(m);
readint(q);
vector<pair<int, ii> > P;
for(int i = 1 ; i <= m ; i++) {
int a, b;
//~ scanf("%d%d", &a, &b);
readint(a);
readint(b);
P.push_back({i, {a, b}});
}
PP = new MasterPoints(P, n);
int cnt = m;
while(q--) {
//~ cout << q << endl;
int t;
//~ scanf("%d", &t);
readint(t);
if(t == 1) {
int i;
//~ scanf("%d", &i);
readint(i);
ii p = PP->query(i);
printf("%d %d\n", p.X, p.Y);
} else if(t == 2) {
int s;
//~ scanf("%d", &s);
readint(s);
PP->sweep_horizontally(s);
} else if(t == 3) {
int s;
//~ scanf("%d", &s);
readint(s);
PP->sweep_vertically(s);
} else {
int a, b;
//~ scanf("%d%d", &a, &b);
readint(a);
readint(b);
PP->add_point(++cnt, a, b);
}
//~ cout << "TREAP\n";
//~ PP->T->print();
}
return 0;
}
