#include <bits/stdc++.h>
using namespace std;
class Sweeping {
private:
struct Point {
int x, y;
Point() {}
Point(int x, int y) : x(x), y(y) {}
};
struct Operation {
int L; // If the operation is of type H, L denotes (N - L[i]) for operation i. L is actually the x-coordinate of the bottomright corner of the triangle formed by the operation, not its length.
bool vertical;
Operation() {}
Operation(int L, bool v) : L(L), vertical(v) {}
bool IsVertical() { return vertical; }
const bool IsVertical() const { return vertical; }
bool operator < (const Operation &o) const { return make_pair(L, vertical) < make_pair(o.L, o.vertical); }
};
class SegmentTree { // Range Minimum Query
private:
int sz;
vector<int> value;
vector<int> tree;
int pull(int a, int b) {
if (a == -1) return b;
if (b == -1) return a;
return value[a] < value[b] ? a : b;
}
public:
void Build(const vector<int> &val, const vector<int> &base) {
sz = val.size();
value = val;
tree.resize(2 * sz);
for (int i = 0; i < sz; i++) {
tree[i + sz] = base[i];
}
for (int i = sz - 1; i >= 0; i--) {
tree[i] = pull(tree[i * 2], tree[i * 2 + 1]);
}
}
int Query(int l, int r) {
int res = -1;
for (l += sz, r += sz + 1; l < r; l /= 2, r /= 2) {
if (l & 1) res = pull(res, tree[l++]);
if (r & 1) res = pull(res, tree[--r]);
}
return res;
}
};
class Transformation { // Given a set of operations Q, find out where point (x, y) will be after all operations
private:
int sz = 0;
int N;
bool isBuilt = false;
vector<Operation> ops; // operations in chronological order
vector<Operation> ops_sorted_L; // sorted by Operation.L
SegmentTree rmq;
void Unique() { // delete multiple elements (since they don't have any effect anyways and make implementation harder)
vector<Operation> new_ops;
set<Operation> unique_ops;
for (int i = 0; i < sz; i++) {
if (unique_ops.count(ops[i]) == 1) {
continue;
}
new_ops.emplace_back(ops[i]);
unique_ops.emplace(ops[i]);
}
ops = new_ops;
sz = ops.size();
}
void Build() {
Unique();
vector<vector<int>> adj(sz);
function<void(int, vector<int>&)> dfs = [&](int u, vector<int> &postorder) {
for (auto &v : adj[u]) dfs(v, postorder); // to compute the minimum value easily. See further for details.
postorder.emplace_back(u);
};
vector<int> roots;
set<pair<Operation, int>> triangles; // (Operation, time in chronological order)
for (int i = 0; i < sz; i++) {
auto it = triangles.lower_bound(make_pair(ops[i], i));
bool isRoot = true;
if (it != end(triangles)) {
if (ops[i].IsVertical() && (*it).first.IsVertical()) {
// if there is an operation H that results in same coordinate, we do not consider it since
// it forms a dot as their triangle, and there is no connection between that dot and curent
// operation, Incidentally, sorting means that an operation H will be encountered in that
// very case, so we do not need to worry about it.
adj[(*it).second].emplace_back(i); // swapping i and it will make no difference - take the one with higher finak y-coordinate.
isRoot = false;
}
}
if (it != begin(triangles)) {
it--;
if (!ops[i].IsVertical() && !(*it).first.IsVertical()) {
// if there is an operation V that results in same coordinate, we do not consider it since
// it forms a dot as their triangle, and there is no connection between that dot and curent
// operation. Incidentally, sorting means that an operation V will be encountered in that
// very case, so we do not need to worry about it.
adj[(*it).second].emplace_back(i);
isRoot = false;
}
}
if (isRoot) {
roots.emplace_back(i);
}
triangles.emplace(ops[i], i);
}
vector<int> new_chronological_order;
for (auto &r : roots) {
dfs(r, new_chronological_order); // postorder dfs
}
vector<int> when(sz), base;
for (int i = 0; i < sz; i++) {
when[new_chronological_order[i]] = i; // compute time values for every indices
}
for (auto &t : triangles) {
ops_sorted_L.emplace_back(t.first); // operation sorted by L
base.emplace_back(t.second); // indices
}
rmq.Build(when, base);
return;
}
Point Transform_(Point p) {
int l = lower_bound(begin(ops_sorted_L), end(ops_sorted_L), Operation(p.x, false)) - begin(ops_sorted_L);
int r = upper_bound(begin(ops_sorted_L), end(ops_sorted_L), Operation(N - p.y, true)) - begin(ops_sorted_L) - 1;
if (l > r) return p;
// [l, r] are regions p can potentially end up in
int mn = rmq.Query(l, r);
if (ops[mn].IsVertical()) {
if (p.x <= ops[mn].L) p.y = max(p.y, N - ops[mn].L);
} else {
if (p.y <= N - ops[mn].L) p.x = max(p.x, ops[mn].L); // ops[mn].L = N - L[i], so L[i] = N - pos[mn].L
}
// update [l, r] after being swept by operation mn
int mn_loc = lower_bound(begin(ops_sorted_L), end(ops_sorted_L), ops[mn]) - begin(ops_sorted_L); // where mn is in ops_sorted_L
if (ops[mn].IsVertical()) {
r = mn_loc - 1; // first is operation V, then operation H
} else {
l = mn_loc + 1; // first is operation H, then operation V
}
if (l > r) return p;
// there is one more operation (if previous is H, then now it's V; vice versa)
mn = rmq.Query(l, r);
if (ops[mn].IsVertical()) {
if (p.x <= ops[mn].L) p.y = max(p.y, N - ops[mn].L);
} else {
if (p.y <= N - ops[mn].L) p.x = max(p.x, ops[mn].L); // ops[mn].L = N - L[i], so L[i] = N - ops[mn].L
}
return p;
}
public:
Transformation() {}
Transformation(int N) : N(N) {}
void AddOperation(const Operation &o) {
ops.emplace_back(o); sz++;
}
Point Transform(Point p) {
if (!isBuilt) isBuilt = true, Build();
return Transform_(p);
}
};
class QueryTree {
private:
int sz;
vector<Transformation> tree;
void AddOperation(int n, int tl, int tr, int pos, const Operation &op) {
tree[n].AddOperation(op);
if (tl == tr) return;
int mid = (tl + tr) / 2;
if (pos <= mid) {
AddOperation(n * 2, tl, mid, pos, op);
} else {
AddOperation(n * 2 + 1, mid + 1, tr, pos, op);
}
}
void Query(int n, int tl, int tr, int l, int r, Point &p) {
if (tr < l || r < tl || tl > tr || l > r) return;
if (l <= tl && tr <= r) return void(p = tree[n].Transform(p));
int mid = (tl + tr) / 2;
Query(n * 2, tl, mid, l, r, p);
Query(n * 2 + 1, mid + 1, tr, l, r, p);
}
public:
QueryTree(int N, int Q) {
sz = Q;
tree.assign(4 * sz, Transformation(N));
}
void AddOperation(int pos, Operation op) {
AddOperation(1, 0, sz - 1, pos, op);
}
Point Query(int l, int r, Point p) {
Query(1, 0, sz - 1, l, r, p);
return p;
}
};
public:
void Solve() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int N, M, Q;
vector<pair<Point, int>> P; // (Point, time_added)
cin >> N >> M >> Q;
QueryTree QTree(N, Q);
for (int i = 0; i < M; i++) {
int x, y; cin >> x >> y;
P.emplace_back(Point(x, y), 0);
}
for (int i = 0, op_cnt = 0; i < Q; i++) {
int T; cin >> T;
if (T == 1) {
int pos; cin >> pos; pos--;
Point res = QTree.Query(P[pos].second, op_cnt - 1, P[pos].first);
cout << res.x << " " << res.y << "\n";
} else if (T == 2 || T == 3) {
int L; cin >> L;
if (T == 2) QTree.AddOperation(op_cnt, Operation(N - L, false)); // operation H
if (T == 3) QTree.AddOperation(op_cnt, Operation(L, true)); // operation V
op_cnt++;
} else if (T == 4) {
int x, y; cin >> x >> y;
P.emplace_back(Point(x, y), op_cnt);
}
}
}
};
int main() {
Sweeping Solver;
Solver.Solve();
return 0;
}
