#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
using namespace std;
#define F first
#define S second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define SZ(x) (int)(x).size()
//#define int ll
struct dust {
int x, y, id;
dust() {};
dust(int x, int y, int id) : x(x), y(y), id(id) {};
};
struct query {
int type, x, id;
dust A;
query() {};
query(int type, int x, int id, dust A) : type(type), x(x), id(id), A(A) {};
};
struct DSU {
vector<int> p, sz, curval;
vector<vector<int>> have;
DSU(int n) {
p.resize(n);
sz.resize(n, 1);
have.resize(n);
curval.resize(n);
iota(all(p), 0);
for (int i = 0; i < n; i++) {
have[i] = {i};
}
}
int find(int v) {
return p[v] == v ? v : p[v] = find(p[v]);
}
int merge(int a, int b) {
a = find(a), b = find(b);
if (a == b) {
return a;
}
if (sz[a] < sz[b]) {
swap(a, b);
}
sz[a] += sz[b];
p[b] = a;
for (auto it : have[b]) {
have[a].pb(it);
}
return a;
}
void update(int v, int x) {
v = find(v);
curval[v] = x;
}
};
int n, iter;
const int N = 1e6 + 10;
pair<int, int> ans[N];
void solve(vector<dust> &have, vector<query> &que, int lx, int rx, int ly, int ry) {
if (que.empty()) {
return;
}
iter++;
int Gx = (lx + rx) / 2, Gy = (ly + ry) / 2;
int sz = SZ(have);
for (auto it : que) {
if (it.type == 4) {
sz++;
}
}
if (sz == 0) {
return;
}
map<int, int> lstx, lsty, num;
DSU Hx(sz), Hy(sz);
vector<dust> toRD, toUD;
vector<query> toRQ, toUQ;
int ptr = 0;
vector<int> kl(sz);
for (auto it : have) {
num[it.id] = ptr;
Hx.update(ptr, it.x);
Hy.update(ptr, it.y);
if (it.x > Gx) {
toRD.pb(it);
kl[ptr] = 1;
}
else if (it.y > Gy) {
toUD.pb(it);
kl[ptr] = 2;
}
else {
if (lstx.find(it.x) != lstx.end()) {
lstx[it.x] = Hx.merge(ptr, lstx[it.x]);
}
else {
lstx[it.x] = ptr;
}
if (lsty.find(it.y) != lsty.end()) {
lsty[it.y] = Hy.merge(ptr, lsty[it.y]);
}
else {
lsty[it.y] = ptr;
}
}
ptr++;
}
for (auto it : que) {
//cout << it.type << endl;
if (it.type == 1) {
if (!kl[num[it.x]]) {
ans[it.id] = {Hx.curval[Hx.find(num[it.x])], Hy.curval[Hy.find(num[it.x])]};
}
else if (kl[num[it.x]] == 1) {
toRQ.pb(it);
}
else {
toUQ.pb(it);
}
}
if (it.type == 2) {
if (it.x > Gy) {
toUQ.pb(it);
}
if (n - it.x > Gx) {
toRQ.pb(it);
}
if (have.empty()) {
continue;
}
if (n - it.x > Gx) {
while (!lsty.empty() && lsty.begin()->F <= it.x) {
int comp = lsty.begin()->S;
for (auto itt : Hy.have[comp]) {
if (!kl[itt]) {
query cur;
cur.type = 4;
cur.A.x = n - it.x;
cur.A.y = Hy.curval[Hy.find(itt)];
cur.A.id = have[itt].id;
toRQ.pb(cur);
kl[itt] = 1;
}
}
lsty.erase(lsty.begin());
}
}
else {
int vl = n - it.x;
if (lstx.begin()->F >= vl) {
continue;
}
int cur = lstx.begin()->S;
while (!lstx.empty() && lstx.begin()->F < vl) {
cur = Hx.merge(lstx.begin()->S, cur);
lstx.erase(lstx.begin());
}
Hx.update(cur, vl);
if (lstx.find(vl) != lstx.end()) {
lstx[vl] = Hx.merge(lstx[vl], cur);
}
else {
lstx[vl] = cur;
}
}
}
if (it.type == 3) {
if (it.x > Gx) {
toRQ.pb(it);
}
if (n - it.x > Gy) {
toUQ.pb(it);
}
if (have.empty()) {
continue;
}
if (n - it.x > Gy) {
while (!lstx.empty() && lstx.begin()->F <= it.x) {
int comp = lstx.begin()->S;
for (auto itt : Hx.have[comp]) {
if (!kl[itt]) {
query cur;
cur.type = 4;
cur.A.id = have[itt].id;
cur.A.x = Hx.curval[Hx.find(itt)];
cur.A.y = n - it.x;
toUQ.pb(cur);
kl[itt] = 2;
}
}
lstx.erase(lstx.begin());
}
}
else {
int vl = n - it.x;
if (lsty.begin()->F >= vl) {
continue;
}
int cur = lsty.begin()->S;
while (!lsty.empty() && lsty.begin()->F < vl) {
cur = Hy.merge(lsty.begin()->S, cur);
lsty.erase(lsty.begin());
}
Hy.update(cur, vl);
if (lsty.find(vl) != lsty.end()) {
lsty[vl] = Hy.merge(lsty[vl], cur);
}
else {
lsty[vl] = cur;
}
}
}
if (it.type == 4) {
num[it.A.id] = SZ(have);
Hx.update(SZ(have), it.A.x);
Hy.update(SZ(have), it.A.y);
have.pb(it.A);
if (it.A.x > Gx) {
toRQ.pb(it);
kl[num[it.A.id]] = 1;
}
else if (it.A.y > Gy) {
toUQ.pb(it);
kl[num[it.A.id]] = 2;
}
else {
if (lstx.find(it.A.x) != lstx.end()) {
lstx[it.A.x] = Hx.merge(lstx[it.A.x], num[it.A.id]);
}
else {
lstx[it.A.x] = num[it.A.id];
}
if (lsty.find(it.A.y) != lsty.end()) {
lsty[it.A.y] = Hy.merge(lsty[it.A.y], num[it.A.id]);
}
else {
lsty[it.A.y] = num[it.A.id];
}
}
}
}
solve(toRD, toRQ, Gx + 1, rx, ly, ly + (rx - Gx - 1));
solve(toUD, toUQ, lx, lx + (ry - Gy - 1), Gy + 1, ry);
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int m, q;
cin >> n >> m >> q;
vector<dust> have;
for (int i = 0; i < m; i++) {
int x, y;
cin >> x >> y;
have.pb(dust(x, y, i + 1));
}
int cnt = m;
vector<query> que;
for (int i = 0; i < q; i++) {
ans[i] = {-1, -1};
query cur;
cur.id = i;
cin >> cur.type;
if (cur.type < 4) {
cin >> cur.x;
}
else {
cin >> cur.A.x >> cur.A.y;
cur.A.id = ++cnt;
}
que.pb(cur);
}
solve(have, que, 0, n, 0, n);
//cout << '\n';
for (int i = 0; i < q; i++) {
if (ans[i].F >= 0) {
cout << ans[i].F << ' ' << ans[i].S << '\n';
}
}
}
