#include <bits/stdc++.h>
using namespace std;
#define ar array
#define sz(v) int(std::size(v))
using i64 = long long;
using pii = pair<int, int>;
const int MAXQ = 15e5;
int N, M, Q;
vector<pii> points;
bool alive[MAXQ];
vector<int> ask; vector<pii> ans;
list<int> under[MAXQ * 2];
int parent[MAXQ * 2];
int p[MAXQ * 2], sz[MAXQ * 2], mx[MAXQ * 2];
int tt;
void clear() {
while (tt > 0)
exchange(under[--tt], {});
}
int newnode(int x, int i) {
int v = tt++;
p[v] = v;
mx[v] = x;
sz[v] = 1;
if (~i) under[v].push_back(i), parent[i] = v;
return v;
}
int find(int i) {
return p[i] == i ? i : p[i] = find(p[i]);
}
int merge(int i, int j) {
i = find(i);
j = find(j);
if (i == j) return i;
if (sz[i] < sz[j]) swap(i, j);
p[j] = i;
sz[i] += sz[j];
mx[i] = max(mx[i], mx[j]);
under[i].splice(end(under[i]), under[j]);
return i;
}
pii qry_point(int i) {
return {mx[find(parent[i * 2])], mx[find(parent[i * 2 + 1])]};
}
void rec(int X, int Y, vector<pii> qry) {
if (sz(qry) == 0) return;
if (X + Y == N) {
for (auto [t, p] : qry) if (t == 1)
ans[p] = points[ask[p]];
} else {
clear();
int x_mid = X + (N - X - Y) / 2 + 1;
int y_mid = N + 1 - x_mid;
vector<pii> qry_one, qry_two;
priority_queue<pii, vector<pii>, greater<pii>> qu_x, qu_y;
for (auto [t, p] : qry) {
if (t == 1) {
int i = ask[p];
if (points[i].first >= x_mid) qry_one.push_back({t, p});
else if (points[i].second >= y_mid) qry_two.push_back({t, p});
else ans[p] = qry_point(i);
} else if (t == 2) {
if (p >= y_mid) {
int v = newnode(N - p, -1);
while (sz(qu_x) && qu_x.top().first < N - p) {
v = merge(v, qu_x.top().second);
qu_x.pop();
}
qry_two.push_back({t, p});
qu_x.push({N - p, v});
} else {
while (sz(qu_y) && qu_y.top().first <= p) {
for (int i : under[qu_y.top().second]) {
i /= 2;
if (alive[i]) {
points[i] = qry_point(i);
points[i].first = N - p;
alive[i] = false;
qry_one.push_back({4, i});
}
}
qu_y.pop();
}
qry_one.push_back({t, p});
}
} else if (t == 3) {
if (p >= x_mid) {
int v = newnode(N - p, -1);
while (sz(qu_y) && qu_y.top().first < N - p) {
v = merge(v, qu_y.top().second);
qu_y.pop();
}
qry_one.push_back({t, p});
qu_y.push({N - p, v});
} else {
while (sz(qu_x) && qu_x.top().first <= p) {
for (int i : under[qu_x.top().second]) {
i /= 2;
if (alive[i]) {
points[i] = qry_point(i);
points[i].second = N - p;
alive[i] = false;
qry_two.push_back({4, i});
}
}
qu_x.pop();
}
qry_two.push_back({t, p});
}
} else if (t == 4) {
if (points[p].first >= x_mid) qry_one.push_back({t, p});
else if (points[p].second >= y_mid) qry_two.push_back({t, p});
else {
alive[p] = 1;
qu_x.push({points[p].first, newnode(points[p].first, p * 2)});
qu_y.push({points[p].second, newnode(points[p].second, p * 2 + 1)});
}
}
}
rec(x_mid, Y, qry_one);
rec(X, y_mid, qry_two);
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> N >> M >> Q;
vector<pii> qry;
points.reserve(M + Q);
ask.reserve(Q);
ans.reserve(Q);
for (int i = 0; i < M + Q; i++) {
int t = 4;
if (i >= M) cin >> t;
if (t == 1) {
int i; cin >> i, i--;
qry.push_back({1, sz(ans)});
ask.push_back(i);
ans.push_back({-1, -1});
} else if (t == 2) {
int l; cin >> l;
qry.push_back({2, l});
} else if (t == 3) {
int l; cin >> l;
qry.push_back({3, l});
} else {
int x, y; cin >> x >> y;
qry.push_back({4, sz(points)});
points.push_back({x, y});
}
}
rec(0, 0, qry);
for (auto [x, y] : ans) cout << x << ' ' << y << '\n';
}
