#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 SegmentTree {
int lv;
vector<pair<int, int> > d;
vector<int> x;
vector<int> ind;
SegmentTree(vector<pair<int, ii>> V) {
int n = V.size();
lv = 2;
while(lv < n + 2)
lv *= 2;
d.resize(2 * lv + 2, {inf, inf});
x.resize(lv + 2, inf);
ind.resize(lv + 2, inf);
for(int i = 0 ; i < V.size() ; i++) {
d[lv + i] = {V[i].Y.Y, i};
x[i] = V[i].Y.X;
ind[i] = V[i].X;
}
for(int i = lv - 1 ; i >= 1 ; i--)
d[i] = min(d[2 * i], d[2 * i + 1]);
}
// ind, {x, y}
ii _query(int a, int b) {
if(b < a)
return {inf, inf};
int va = lv + a;
int vb = lv + b;
auto res = min(d[va], d[vb]);
while(va / 2 != vb / 2) {
if(va % 2 == 0)
res = min(res, d[va + 1]);
if(vb % 2 == 1)
res = min(res, d[vb - 1]);
va /= 2;
vb /= 2;
}
return res;
}
void insert(int w, int v) {
w += lv;
d[w].X = v;
w /= 2;
while(w) {
d[w] = min(d[2 * w], d[2 * w + 1]);
w /= 2;
}
}
// x <= l
pair<int, ii> query(int l, int y) {
auto it = upper_bound(x.begin(), x.end(), l);
int a = 0;
int b = distance(x.begin(), it) - 1;
ii p = _query(a, b);
if(p.X > y)
return {-1, {-1, -1}};
insert(p.Y, inf);
return {ind[p.Y], {x[p.Y], p.X}};
}
};
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;
}
};
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;
set<int> on_treap;
map<int, ii> initial_cor;
static bool compp(const pair<int, ii> &a, const pair<int, ii> &b) {
return a.Y.X < b.Y.X;
}
Points(vector<pair<int, ii> > &P, int n) {
this->n = n;
T = new Treap();
m = P.size();
sort(P.begin(), P.end(), compp);
ST = new SegmentTree(P);
for(auto p : P)
initial_cor[p.X] = p.Y;
}
~Points() {
delete T;
delete ST;
}
ii query(int i) {
if(on_treap.count(i))
return T->query(i);
else
return initial_cor[i];
}
void sweep_horizontally(int s) {
T->maxx(s, n - s);
pair<int, ii> p;
while((p = ST->query(n - s, s)).X != -1) {
T->insert(p.X, n - s, p.Y.Y);
on_treap.insert(p.X);
}
}
void sweep_vertically(int s) {
T->maxy(s, n - s);
pair<int, ii> p;
while((p = ST->query(s, n - s)).X != -1) {
T->insert(p.X, p.Y.X, n - s);
on_treap.insert(p.X);
}
}
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.count(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;
}
