//#define LOCAL
#include <bits/stdc++.h>
#include <cassert>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define MAX 2010101
#define MAXQ 101010
#define INF 1'000'000'100
#define bb ' '
#define ln '\n'
#define Ln '\n'
#define MOD 1000000007
#define TC 1
#ifdef LOCAL
#define DEBUG(a) cout<<a
#define TEST true
#else
#define DEBUG(...) 1234
#define TEST false
#endif
int N, M, Q;
//points
int X[MAX];
int Y[MAX];
int S[MAX];
vector<int> es[MAX];
//queries
int T[MAX];
int L[MAX];
pii ans[MAX];
vector<int> qv[MAX];
struct node {
int val;
int key;
int p, n;
int lnk;
node(int k = 0, int v = 0, int p = 0, int n = 0) :p(p), n(n) {
val = v;
key = k;
lnk = 0;
}
};
vector<node> MEM;
void disc(int n) {
if (MEM[n].p) MEM[MEM[n].p].n = MEM[n].n;
if (MEM[n].n) MEM[MEM[n].n].p = MEM[n].p;
MEM[n].p = MEM[n].n = 0;
}
int make_node(int k, int v, int p = 0, int n = 0) {
int s = MEM.size();
MEM.push_back(node(k, v, p, n));
return s;
}
struct Dat {
int sv[2] = { 0, 0 }; //linked list
int ev[2] = { 0, 0 };
int cap[2] = { 0, 0 }; //cap from down
int N;
void init(vector<int> K, vector<vector<int>> X) {
vector<pii> ord;
N = K.size();
int i;
for (i = 0; i < N; i++) ord.emplace_back(i, 0);
sort(ord.begin(), ord.end(), [&](pii i, pii j) {return X[0][i.first] < X[0][j.first]; });
int pv = 0;
for (auto& v : ord) {
int nn = make_node(K[v.first], X[0][v.first], pv);
if (!sv[0]) sv[0] = nn;
ev[0] = nn;
v.second = nn;
if (pv) MEM[pv].n = nn;
pv = nn;
}
sort(ord.begin(), ord.end(), [&](pii i, pii j) {return X[1][i.first] < X[1][j.first]; });
pv = 0;
for (auto& v : ord) {
int nn = make_node(K[v.first], X[1][v.first], pv);
if (!sv[1]) sv[1] = nn;
ev[1] = nn;
if (pv) MEM[pv].n = nn;
MEM[nn].lnk = v.second;
MEM[v.second].lnk = nn;
pv = nn;
}
}
int& begin(int c) { return sv[c]; }
int& rbegin(int c) { return ev[c]; }
node& front(int c) { return MEM[sv[c]]; }
node& back(int c) { return MEM[ev[c]]; }
};
vector<Dat> lists;
int flag; // flag for divide function
int divide(Dat& D, int c, int L) {
int op = c ^ 1;
int n = D.N;
if (max(D.cap[c], D.front(c).val) >= L) {
flag = 0;
return -1;
}
if (max(D.cap[c], D.back(c).val) < L) {
flag = 1;
return -1;
}
int i;
int chk = 0;
int rem = 0; // remove
int s, e;
s = D.begin(c);
e = D.rbegin(c);
for (i = 0; i < n; i++) {
if (max(D.cap[c], MEM[s].val) >= L) {
chk = 0;
rem = i;
break;
}
if (max(D.cap[c], MEM[e].val) < L) {
chk = 1;
rem = i;
break;
}
s = MEM[s].n;
e = MEM[e].p;
}
Dat nd;
nd.cap[0] = D.cap[0];
nd.cap[1] = D.cap[1];
s = D.begin(c);
e = D.rbegin(c);
nd.N = rem;
if (chk) { //remove from back
e = D.rbegin(c);
vector<int> rems;
for (i = 0; i < rem; i++) {
int opn = MEM[e].lnk;
assert(opn);
assert(e);
if (opn == D.begin(op)) D.begin(op) = MEM[opn].n;
if (opn == D.rbegin(op)) D.rbegin(op) = MEM[opn].p;
disc(opn);
rems.push_back(opn);
e = MEM[e].p;
}
int ns = MEM[e].n; // [list 1(original)] ... e / ns ... [list 2(new)]
MEM[e].n = 0;
MEM[ns].p = 0;
// D.sv[op], D.ev[op] is correct
sort(rems.begin(), rems.end());
for (i = 1; i < rem; i++) {
MEM[rems[i - 1]].n = rems[i];
MEM[rems[i]].p = rems[i - 1];
assert(MEM[rems[i - 1]].val <= MEM[rems[i]].val);
}
nd.sv[c] = ns;
nd.sv[op] = rems[0];
nd.ev[c] = D.ev[c];
nd.ev[op] = rems.back();
D.ev[c] = e;
flag = 0;
}
else { // remove from front
s = D.begin(c);
vector<int> rems;
for (i = 0; i < rem; i++) {
int opn = MEM[s].lnk;
assert(opn);
assert(e);
if (opn == D.begin(op)) D.begin(op) = MEM[opn].n;
if (opn == D.rbegin(op)) D.rbegin(op) = MEM[opn].p;
disc(opn);
rems.push_back(opn);
s = MEM[s].n;
}
int ne = MEM[s].p; // [list 1(new)] ... ne / s ... [list 2(original)]
MEM[s].p = 0;
MEM[ne].n = 0;
// D.sv[op], D.ev[op] is correct
sort(rems.begin(), rems.end());
for (i = 1; i < rem; i++) {
MEM[rems[i - 1]].n = rems[i];
MEM[rems[i]].p = rems[i - 1];
}
nd.sv[c] = D.sv[c];
nd.sv[op] = rems[0];
nd.ev[c] = ne;
nd.ev[op] = rems.back();
D.sv[c] = s;
flag = 1;
}
D.N = n - rem;
lists.push_back(nd);
return lists.size() - 1;
}
void solve(int l, int r, vector<int>& v) {
lists.clear();
MEM.clear();
MEM.push_back(node());
int i;
int n = v.size();
vector<int> K(n);
vector<vector<int>> val(2, vector<int>(K.size()));
for (i = 0; i < n; i++) {
K[i] = v[i];
val[0][i] = X[v[i]];
val[1][i] = Y[v[i]];
}
Dat d;
d.init(K, val);
lists.push_back(d);
set<pii> st; // (left top point of the triangle, index in lists)
st.emplace(-2, 0);
for (i = l; i <= r; i++) {
if (T[i] == 1 || T[i] == 4) continue;
if (T[i] == 2) {
int v = N - L[i];
auto it = st.lower_bound(pii(v, 0));
it--;
int pv = it->first;
int ind1 = it->second;
st.erase(it);
int ind2 = divide(lists[ind1], 1, L[i] + 1);
if (!~ind2) {
if (flag) lists[ind1].cap[0] = max(lists[ind1].cap[0], v);
st.emplace(pv, ind1);
continue;
}
if (flag) { //reversed
st.emplace(pv, ind1);
st.emplace(v, ind2);
lists[ind2].cap[0] = max(lists[ind2].cap[0], v);
}
else {
st.emplace(pv, ind2);
st.emplace(v, ind1);
lists[ind1].cap[0] = max(lists[ind1].cap[0], v);
}
}
else {
int v = N - L[i];
auto it = st.lower_bound(pii(L[i] + 1, 0));
it--;
int pv = it->first;
int ind1 = it->second;
st.erase(it);
int ind2 = divide(lists[ind1], 0, L[i] + 1);
if (!~ind2) {
if (flag) lists[ind1].cap[1] = max(lists[ind1].cap[1], v);
st.emplace(pv, ind1);
continue;
}
if (flag) { //reversed
st.emplace(pv, ind2);
st.emplace(L[i], ind1);
lists[ind2].cap[1] = max(lists[ind2].cap[1], v);
}
else {
st.emplace(pv, ind1);
st.emplace(L[i], ind2);
lists[ind1].cap[1] = max(lists[ind1].cap[1], v);
}
}
}
for (auto& d : lists) {
assert(!MEM[d.sv[0]].p);
assert(!MEM[d.sv[1]].p);
assert(!MEM[d.ev[0]].n);
assert(!MEM[d.ev[1]].n);
int s = d.sv[0];
for (i = 0; i < d.N; i++) {
int v = MEM[s].key;
X[v] = max(X[v], d.cap[0]);
Y[v] = max(Y[v], d.cap[1]);
if (qv[v].size() && qv[v].back() == r) {
ans[qv[v].back()] = pii(X[v], Y[v]);
qv[v].pop_back();
}
s = MEM[s].n;
}
}
}
vector<int> tree[MAX * 4];
vector<tuple<int, int, int>> vt;
void init(int s, int e, int loc = 1) {
vt.emplace_back(s, e, loc);
if (s == e) return;
int m = s + e >> 1;
init(s, m, loc * 2);
init(m + 1, e, loc * 2 + 1);
}
void add(int s, int e, int l, int r, int v, int loc = 1) {
if (e < l || r < s) return;
if (l <= s && e <= r) {
tree[loc].push_back(v);
return;
}
int m = s + e >> 1;
add(s, m, l, r, v, loc * 2);
add(m + 1, e, l, r, v, loc * 2 + 1);
}
#ifdef LOCAL
#define cin fin
ifstream fin("C:\\Users\\flapp\\Downloads\\sweeping-data\\in\\04-10.txt");
#endif
signed main() {
#ifndef LOCAL
ios::sync_with_stdio(false), cin.tie(0);
#endif
cin >> N >> M >> Q;
int i, x;
for (i = 1; i <= M; i++) {
cin >> X[i] >> Y[i];
S[i] = 1;
}
init(1, Q);
for (i = 1; i <= Q; i++) {
cin >> T[i];
if (T[i] == 1) {
cin >> x;
if (qv[x].empty()) add(1, Q, S[x], i, x);
else add(1, Q, qv[x].back() + 1, i, x);
qv[x].push_back(i);
}
if (T[i] == 2 || T[i] == 3) cin >> L[i];
if (T[i] == 4) {
S[++M] = i;
cin >> X[M] >> Y[M];
}
}
for (i = 1; i <= M; i++) reverse(qv[i].begin(), qv[i].end());
sort(vt.begin(), vt.end());
for (auto& [l, r, v] : vt) if (tree[v].size()) solve(l, r, tree[v]);
for (i = 1; i <= Q; i++) if (T[i] == 1) cout << ans[i].first << bb << ans[i].second << ln;
}
