#include <bits/stdc++.h>
#define all(x) begin(x), end(x)
using namespace std;
using ll = long long;
struct Query {
int type, v, x, y;
};
struct RectSweep {
map<int, vector<int>> CtoP[2];
vector<array<int, 2>> pts;
vector<int> real_id;
map<int, int> local_id;
vector<int> pt_color[2];
vector<int> col_coord[2];
void addPoint(array<int, 2> P, int id) {
for(int i = 0; i < 2; i++) {
CtoP[i][P[i]].push_back(pts.size());
if(CtoP[i][P[i]].size() == 1) {
pt_color[i].push_back(col_coord[i].size());
col_coord[i].push_back(P[i]);
} else {
pt_color[i].push_back(pt_color[i][CtoP[i][P[i]][0]]);
}
}
real_id.push_back(id);
local_id[id] = pts.size();
pts.push_back(P);
}
void combine(vector<int> &a, vector<int> &b, int dir) {
if(a.size() < b.size()) swap(a, b);
for(auto &i : b) {
a.push_back(i);
pt_color[dir][i] = pt_color[dir][a[0]];
}
}
void sweep(int dir, int lim) {//coord_dir max=
while(CtoP[dir].size() && CtoP[dir].begin()->first < lim) {
combine(CtoP[dir][lim], CtoP[dir].begin()->second, dir);
CtoP[dir].erase(CtoP[dir].begin());
int col = pt_color[dir][CtoP[dir][lim][0]];
col_coord[dir][col] = lim;
}
}
vector<array<int, 3>> extract(int dir, int lim) {//delete coord_dir <= lim
vector<array<int, 3>> res;
while(CtoP[dir].size() && CtoP[dir].begin()->first <= lim) {
for(auto i : CtoP[dir].begin()->second) {
if(real_id[i] != -1) {
int X = col_coord[0][pt_color[0][i]];
int Y = col_coord[1][pt_color[1][i]];
res.push_back({real_id[i], X, Y});
real_id[i] = -1 - dir;
}
}
CtoP[dir].erase(CtoP[dir].begin());
}
return res;
}
array<int, 2> getPoint(int rid) {
if(!local_id.count(rid)) return {-1, -1};//never inserted
int lid = local_id[rid];
if(real_id[lid] < 0) return {-1, -1};//point already extracted
return {col_coord[0][pt_color[0][lid]],
col_coord[1][pt_color[1][lid]]};
}
};
void test_rs() {
RectSweep rs;
rs.addPoint({3, 3}, 100);
rs.addPoint({0, 0}, 1);
rs.sweep(0, 10);
for(auto [i, x, y] : rs.extract(1, 0)) cout << i << " " << x << " " << y << "; "; cout << endl;
rs.addPoint({0, 0}, 10);
rs.sweep(1, 12);
rs.sweep(0, 3);
for(auto [i, x, y] : rs.extract(0, 9)) cout << i << " " << x << " " << y << "; "; cout << endl;
for(auto [i, x, y] : rs.extract(0, 10)) cout << i << " " << x << " " << y << "; "; cout << endl;
exit(0);
}
void solve(int n, vector<Query> queries, vector<array<int, 2>> &ans, int start_x, int start_y) {
if(queries.empty()) return;
// cout << "_____"<<endl;
// cout << n << " " << queries.size() << " cc " << start_x << " " << start_y << endl;
// for(auto &q : queries) {
// cout << q.type << " " << q.v << " " << q.x << " " << q.y << endl;
// }
int r = n / 2;
array<vector<Query>, 2> push;//0 for top, 1 for right
map<int, int> point_dir;
RectSweep rc;
for(auto q : queries) {
if(q.type == 1) {
auto [x, y] = rc.getPoint(q.v);
if(x >= 0) {
ans[q.x] = {start_x + x, start_y + y};
// cout << q.x << " :: " << q.v << " " << start_x << " " << start_y << " " << x << " " << y << endl;
} else {
assert(point_dir.count(q.v));
push[point_dir[q.v]].push_back(q);
}
}
if(q.type == 2 || q.type == 3) {
int dir = 3 - q.type;
int len = q.v;
// For all P[dir]<=len, P[dir ^ 1] = n - len
if(n - len > r) {//go up/right
for(auto [id, x, y] : rc.extract(dir, len)) {
point_dir[id] = dir;
(dir ? x : y) = n - len;
push[dir].push_back(Query{4, id, x, y});
}
push[dir].push_back(q);
} else {//P[dir ^ 1] max= n-len for all
rc.sweep(dir ^ 1, n - len);
q.v -= r + 1;
if(q.v >= 0)
push[dir ^ 1].push_back(q);
}
}
if(q.type == 4) {
if(q.y > r) {
point_dir[q.v] = 0;
push[0].push_back(q);
} else if(q.x > r) {
point_dir[q.v] = 1;
push[1].push_back(q);
} else {
// cout << "Add " << q.x << " " << q.y << " " << q.v << endl;
rc.addPoint({q.x, q.y}, q.v);
// cout << rc.getPoint(q.v)[1] << endl;
}
}
}
for(int c = 0; c < 2; c++) {
for(auto &q : push[c]) {
if(q.type == 4) {
(c ? q.x : q.y) -= r+1;
}
}
}
solve(n - r - 1, push[0], ans, start_x, start_y + r + 1);
solve(n - r - 1, push[1], ans, start_x + r + 1, start_y);
}
int main() {
cin.tie(0)->sync_with_stdio(0);
// test_rs();
int n, m, q;
int num_points = 0, num_ask = 0;
cin >> n >> m >> q;
vector<Query> queries(m + q);
for(int x, y, i = 0; i < m; i++) {
cin >> x >> y;
queries[i] = Query{4, num_points++, x, y};
}
for(int i = 0; i < q; i++) {
cin >> queries[m+i].type;
if(queries[m+i].type == 4) {
cin >> queries[m+i].x >> queries[m+i].y;
queries[m+i].v = num_points++;
} else {
cin >> queries[m + i].v;
queries[m + i].v -= (queries[m+i].type == 1);
if(queries[m+i].type == 1) {
queries[m+i].x = num_ask++;
}
}
}
vector<array<int, 2>> answers(num_ask);
solve(n, queries, answers, 0, 0);
for(auto [x, y] : answers) {
cout << x << ' ' << y << '\n';
}
}
