题目描述

题目译自 JOISC 2020 Day1 T3「掃除 / Sweeping」

Bitaro 的房间是一个边长为 $N$ 的等腰直角三角形。房间内一点用坐标 $(x,y)$ 表示，其中 $0\le x\le N$，$0\le y\le N$，$x+y\le N$。直角顶点为原点，三角形两腰分别为 $x$ 轴与 $y$ 轴。

一天，Bitaro 注意到他的房间满是灰尘。初始时，房间内有 $M$ 堆灰尘。第 $i\ (1\le i\le M)$ 堆灰尘位于点 $(X_i,Y_i)$。在同一点可能有多堆灰尘。

现在，Bitaro 打算用扫帚打扫房间。我们认为扫帚是在房间里的一条线段，并且称线段的长度为扫帚的宽度。因为 Bitaro 做事很有条理，他只能按如下两种方式使用扫帚：

1. 过程 H：Bitaro 将扫帚放在房间里，使得扫帚的一个端点位于原点，并且扫帚平行于 $y$ 轴。然后，他会沿 $x$ 轴正方向水平移动扫帚，直到不能移动为止。在移动过程中，他会保证扫帚始终与 $y$ 轴平行，并且一个端点始终在 $x$ 轴上。如果扫帚宽度为 $l$，则在 $(x,y)$ 位置的灰尘（$x<N-l$，$y\le l$）将会移动到 $(N-l,y)$（在 $(N-l,y)$ 处可能存在其他堆灰尘）。
2. 过程 V：Bitaro 将扫帚放在房间里，使得扫帚的一个端点位于原点，并且扫帚平行于 $x$ 轴。然后，他会沿 $y$ 轴正方向水平移动扫帚，直到不能移动为止。在移动过程中，他会保证扫帚始终与 $x$ 轴平行，并且一个端点始终在 $y$ 轴上。如果扫帚宽度为 $l$，则在 $(x,y)$ 位置的灰尘（$x\le l$，$y<N-l$）将会移动到 $(x,N-l)$（在 $(x,N-l)$ 处可能存在其他堆灰尘）。

在 Bitaro 的房间里，会按顺序发生 $Q$ 个事件。第 $j\ (1\le j\le Q)$ 个事件是以下事件中的一个：

1. 类型 1：Bitaro 计算第 $P_j$ 堆灰尘的位置坐标；
2. 类型 2：Bitaro 使用宽度为 $L_j$ 的扫帚，进行了过程 H；
3. 类型 3：Bitaro 使用宽度为 $L_j$ 的扫帚，进行了过程 V；
4. 类型 4：一堆新灰尘出现在点 $(A_j,B_j)$ 处。如果在这个事件之前一共有 $c$ 堆灰尘，那么这堆灰尘就是房间中的第 $(c+1)$ 堆灰尘。

写一个程序，给出房间的腰长，每一堆灰尘的位置坐标和每个事件的细节，求出要求的某堆灰尘的位置坐标。

---

输入格式

从标准输入读入以下数据，所有输入的值均为整数。

第一行三个整数，分别为 $N,M,Q$。

接下来 $M$ 行，每行两个整数 $X_i,Y_i$，表示第 $i$ 堆灰尘的初始坐标。

接下来 $Q$ 行，每行表示一个事件，有两或三个整数。设 $T_j$ 为第一个整数，每行含义如下：

• 如果 $T_j=1$，则这行有两个整数 $T_j,P_j$。表示 Bitaro 要计算第 $P_j$ 堆灰尘的坐标；
• 如果 $T_j=2$，则这行有两个整数 $T_j,L_j$。表示 Bitaro 用宽度为 $L_j$ 的扫帚进行了过程 H；
• 如果 $T_j=3$，则这行有两个整数 $T_j,L_j$。表示 Bitaro 用宽度为 $L_j$ 的扫帚进行了过程 V；
• 如果 $T_j=4$，则这行有三个整数 $T_j,A_j,B_j$。表示一堆新的灰尘出现在 $(A_j,B_j)$ 位置。

---

输出格式

对于每个 $T_j=1$ 的事件，输出一行两个整数到标准输出。输出在事件 $j$ 发生时第 $P_j$ 堆灰尘的位置坐标。

---

样例 1

输入：

6 2 10
1 1
4 0
4 2 3
3 3
1 1
4 1 2
2 3
2 0
1 4
3 2
1 3
1 2

输出：

1 3
3 2
3 3
6 0

初始时，第一堆灰尘位于 $(1,1)$，第二堆灰尘位于 $(4,0)$。

事件解释：

1. 添加第三堆灰尘 $(2,3)$。

2. 过程 V，$l=3$，第一堆灰尘移动到 $(1,3)$。

3. 查询第一堆灰尘 → $(1,3)$。

4. 

5. 添加第四堆灰尘 $(1,2)$。

6. 

7. 过程 H，$l=3$，第一堆灰尘到 $(3,3)$，第三堆灰尘到 $(3,3)$，第四堆灰尘到 $(3,2)$。

8. 

9. 过程 H，$l=0$，第二堆灰尘到 $(6,0)$。

10. 

11. 查询第四堆灰尘 → $(3,2)$。

12. 

13. 过程 V，$l=2$，无影响。

14. 查询第三堆灰尘 → $(3,3)$。

15. 查询第二堆灰尘 → $(6,0)$。

---

样例 2

输入：

9 4 8
2 3
3 1
1 6
4 3
2 6
1 3
2 2
1 4
2 3
1 2
2 4
1 1

输出：

3 6
4 3
7 1
6 3

---

样例 3

输入：

8 1 8
1 5
4 4 1
2 6
1 2
2 3
4 2 2
2 5
1 1
1 3

输出：

4 1
3 5
3 2

---

样例 4

输入：

7 4 9
1 5
2 2
4 2
5 0
2 6
2 3
1 2
3 6
1 4
3 1
1 1
2 2
1 3

输出：

4 2
5 1
1 6
5 2

---

样例 5

输入：

20 5 25
10 6
0 4
2 1
1 0
2 3
2 18
3 9
4 1 5
4 0 2
3 10
4 3 3
3 3
2 9
4 9 1
3 12
1 4
3 19
1 3
1 9
2 1
1 7
1 6
4 3 3
1 10
1 1
1 5
2 0
1 2
2 2
1 7

输出：

2 17
2 17
9 8
0 17
1 17
3 3
10 10
2 17
2 17
0 17

---

数据范围与提示

对于全部数据：

• $1\le N\le 10^9$
• $1\le M\le 5\times 10^5$
• $1\le Q\le 10^6$

保证：

• $0\le X_i,Y_i\le N$，$X_i+Y_i\le N\ (1\le i\le M)$；
• $1\le P_j\le M'\ (1\le j\le Q)$，其中 $M'$ 表示当事件 $j$ 发生时灰尘的堆数；
• $0\le L_j\le N-1\ (1\le j\le Q)$；
• $0\le A_j,B_j\le N$，$A_j+B_j\le N\ (1\le j\le Q)$；
• 存在至少一个事件 $T_j=1\ (1\le j\le Q)$。

详细子任务与附加限制如下表：

子任务	附加限制	分值
1	$M\le 2\times 10^3$，$Q\le 5\times 10^3$	1
2	$T_j=1,2,4$	10
3	$T_j=1,2,3$，$X_j\le X_{j+1}$，$Y_j\ge Y_{j+1}\ (1\le j\le M-1)$	11
4	$T_j=1,2,3$	53
5	无附加限制	25