// chrono::system_clock::now().time_since_epoch().count()
#include<bits/stdc++.h>
//#include<ext/pb_ds/tree_policy.hpp>
//#include<ext/pb_ds/assoc_container.hpp>
#define __DBG 1
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define debug(x) if (__DBG) cerr << #x << " = " << x << endl;
using namespace std;
//using namespace __gnu_pbds;
//template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, pii> que;
const int MAXN = (int)2e6 + 5;
int par[MAXN * 2];
pii arr[MAXN], ans[MAXN];
bool del[MAXN];
int n, m, q;
struct DSU {
vector<int> val;
vector<vector<int>> comp;
void init() {
val.clear();
comp.clear();
}
int add(int v, int label) {
int idx = val.size();
val.pb(v);
comp.pb({});
if (label != -1) {
par[label] = idx;
comp[idx].pb(label);
}
return idx;
}
int uni(int a, int b) {
assert(a != b);
if (comp[a].size() < comp[b].size()) {
swap(a, b);
}
val[a] = max(val[a], val[b]);
for (int x : comp[b]) {
par[x] = a;
comp[a].pb(x);
}
comp[b].clear();
return a;
}
} D;
struct cmp {
bool operator()(const int &a, const int &b) {
return D.val[a] > D.val[b];
}
};
pii coords(int idx) {
return mp(D.val[par[idx * 2]], D.val[par[idx * 2 + 1]]);
}
void rec(int x, int y, vector<que> vec) {
if (vec.empty()) {
return;
}
if (x + y == n) {
for (que it : vec) {
if (it.fi == 1) {
ans[it.se.se] = mp(x, y);
}
}
return;
}
int dif = n - (x + y);
int nx = x + (dif + 1) / 2;
int ny = y + dif / 2 + 1;
D.init();
priority_queue<int, vector<int>, cmp> X, Y;
vector<que> vecR, vecU;
for (que it : vec) {
int tp = it.fi;
if (tp == 1) {
int p = it.se.fi;
int id = it.se.se;
if (arr[p].fi >= nx) {
vecR.pb(it);
}
else if (arr[p].se >= ny) {
vecU.pb(it);
}
else {
ans[id] = coords(p);
}
}
else if (tp == 2) {
// H
// y <= L: x = max(x, n - L)
int L = it.se.fi;
if (L >= ny) {
int z = n - L;
int ver = D.add(z, -1);
while (!X.empty() && D.val[X.top()] <= z) {
int cur = X.top();
X.pop();
ver = D.uni(ver, cur);
}
X.push(ver);
vecU.pb(it);
}
else {
vector<int> rm;
while (!Y.empty() && D.val[Y.top()] <= L) {
int cur = Y.top();
Y.pop();
for (int idx : D.comp[cur]) {
idx /= 2;
if (!del[idx]) {
arr[idx] = coords(idx);
arr[idx].fi = n - L;
del[idx] = 1;
vecR.pb(mp(4, mp(idx, -1)));
}
}
}
vecR.pb(it);
}
}
else if (tp == 3) {
// V
// x <= L: y = max(y, n - L)
int L = it.se.fi;
if (L >= nx) {
int z = n - L;
int ver = D.add(z, -1);
while (!Y.empty() && D.val[Y.top()] <= z) {
int cur = Y.top();
Y.pop();
ver = D.uni(ver, cur);
}
Y.push(ver);
vecR.pb(it);
}
else {
while (!X.empty() && D.val[X.top()] <= L) {
int cur = X.top();
X.pop();
for (int idx : D.comp[cur]) {
idx /= 2;
if (!del[idx]) {
arr[idx] = coords(idx);
arr[idx].se = n - L;
del[idx] = 1;
vecU.pb(mp(4, mp(idx, -1)));
}
}
}
vecU.pb(it);
}
}
else {
int p = it.se.fi;
del[p] = 0;
if (arr[p].fi >= nx) {
del[p] = 1;
vecR.pb(it);
}
else if (arr[p].se >= ny) {
del[p] = 1;
vecU.pb(it);
}
else {
X.push(D.add(arr[p].fi, 2 * p));
Y.push(D.add(arr[p].se, 2 * p + 1));
}
}
}
rec(nx, y, vecR);
rec(x, ny, vecU);
}
void solve() {
scanf("%d %d %d", &n, &m, &q);
vector<que> vec;
for (int i = 1; i <= m; ++i) {
scanf("%d %d", &arr[i].fi, &arr[i].se);
vec.pb(mp(4, mp(i, -1)));
}
for (int i = 1; i <= q; ++i) {
ans[i] = mp(-1, -1);
int tp;
scanf("%d", &tp);
if (tp <= 3) {
int p;
scanf("%d", &p);
vec.pb(mp(tp, mp(p, i)));
}
else {
int x, y;
scanf("%d %d", &x, &y);
arr[++m] = mp(x, y);
vec.pb(mp(tp, mp(m, i)));
}
}
rec(0, 0, vec);
for (int i = 1; i <= q; ++i) {
if (ans[i] != mp(-1, -1)) {
printf("%d %d\n", ans[i].fi, ans[i].se);
}
}
}
int main() {
int tt = 1;
while (tt--) {
solve();
}
return 0;
}
