Bitaro 的房间是一个等腰直角三角形，其直角边长度为 $N$。Bitaro 房间内的一点可以用坐标 $(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 做事井井有条，他只能通过以下两种方式使用扫帚：

• Bitaro 将扫帚放置在房间内，使其一个端点位于原点，且扫帚平行于 $y$ 轴。然后，他将扫帚沿 $x$ 轴正方向尽可能地水平移动，同时保持其平行于 $y$ 轴且一个端点位于 $x$ 轴上。如果扫帚的宽度为 $l$，则位于 $(x, y)$ 且满足 $x < N - l$ 且 $y \le l$ 的灰尘将被移动到 $(N - l, y)$（在 $(N - l, y)$ 处可能已经存在其他灰尘）。这被称为过程 H。
• Bitaro 将扫帚放置在房间内，使其一个端点位于原点，且扫帚平行于 $x$ 轴。然后，他将扫帚沿 $y$ 轴正方向尽可能地垂直移动，同时保持其平行于 $x$ 轴且一个端点位于 $y$ 轴上。如果扫帚的宽度为 $l$，则位于 $(x, y)$ 且满足 $x \le l$ 且 $y < N - l$ 的灰尘将被移动到 $(x, N - l)$（在 $(x, N - l)$ 处可能已经存在其他灰尘）。这被称为过程 V。

在 Bitaro 的房间里，将依次发生 $Q$ 个事件。事件 $j$ ($1 \le j \le Q$) 是以下之一：

• Bitaro 计算灰尘 $P_j$ 的坐标。
• Bitaro 使用宽度为 $L_j$ 的扫帚执行过程 H。
• Bitaro 使用宽度为 $L_j$ 的扫帚执行过程 V。
• 在点 $(A_j, B_j)$ 处添加一处新灰尘。如果在此事件之前有 $c$ 处灰尘，则新灰尘是房间里的第 $(c + 1)$ 处灰尘。

编写一个程序，在给定房间直角边长度、房间内灰尘的初始坐标以及事件详情的情况下，计算灰尘的坐标。

输入格式

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

$N \ M \ Q$ $X_1 \ Y_1$ $\vdots$ $X_M \ Y_M$ (Query 1) $\vdots$ (Query Q)

每个 (Query $j$) ($1 \le j \le Q$) 中包含两个或三个空格分隔的整数。令 $T_j$ 为第一个整数。该行的含义如下：

• 如果 $T_j = 1$，该行包含两个整数 $T_j, P_j$。这意味着在事件 $j$ 中，Bitaro 计算灰尘 $P_j$ 的坐标。
• 如果 $T_j = 2$，该行包含两个整数 $T_j, L_j$。这意味着在事件 $j$ 中，Bitaro 使用宽度为 $L_j$ 的扫帚执行过程 H。
• 如果 $T_j = 3$，该行包含两个整数 $T_j, L_j$。这意味着在事件 $j$ 中，Bitaro 使用宽度为 $L_j$ 的扫帚执行过程 V。
• 如果 $T_j = 4$，该行包含三个整数 $T_j, A_j, B_j$。这意味着在事件 $j$ 中，在点 $(A_j, B_j)$ 处添加一处新灰尘。

输出格式

对于每个 $T_j = 1$ 的事件，向标准输出写入一行。输出事件 $j$ 发生时灰尘 $P_j$ 的 $x$ 坐标和 $y$ 坐标。

数据范围

• $1 \le N \le 1\,000\,000\,000$
• $1 \le M \le 500\,000$
• $1 \le Q \le 1\,000\,000$
• $0 \le X_i \le N$ ($1 \le i \le M$)
• $0 \le Y_i \le N$ ($1 \le i \le M$)
• $X_i + Y_i \le N$ ($1 \le i \le M$)
• $1 \le P_j \le$ (事件 $j$ 发生时灰尘的总数) ($1 \le j \le Q$)
• $0 \le L_j \le N - 1$ ($1 \le j \le Q$)
• $0 \le A_j \le N$ ($1 \le j \le Q$)
• $0 \le B_j \le N$ ($1 \le j \le Q$)
• $A_j + B_j \le N$ ($1 \le j \le Q$)
• 至少存在一个 $T_j = 1$ 的事件 ($1 \le j \le Q$)

子任务

1. (1 分) $M \le 2\,000, Q \le 5\,000$
2. (10 分) $T_j = 1, 2, 4$
3. (11 分) $T_j = 1, 2, 3, X_j \le X_{j+1}, Y_j \ge Y_{j+1}$ ($1 \le j \le M - 1$)
4. (53 分) $T_j = 1, 2, 3$
5. (25 分) 无附加限制

样例

样例输入 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

1 3
3 2
3 3
6 0

说明

• 起初，第 1 处灰尘位于 $(1, 1)$，第 2 处灰尘位于 $(4, 0)$。
• 在事件 1 中，第 3 处灰尘被添加到点 $(2, 3)$。
• 在事件 2 中，Bitaro 使用宽度为 3 的扫帚执行过程 V。随后，第 1 处灰尘被移动到 $(1, 3)$。
• 在事件 3 中，Bitaro 计算第 1 处灰尘的坐标 $(1, 3)$。
• 在事件 4 中，第 4 处灰尘被添加到点 $(1, 2)$。
• 在事件 5 中，Bitaro 使用宽度为 3 的扫帚执行过程 H。随后，第 1 处灰尘被移动到 $(3, 3)$，第 3 处灰尘被移动到 $(3, 3)$，第 4 处灰尘被移动到 $(3, 2)$。
• 在事件 6 中，Bitaro 使用宽度为 0 的扫帚执行过程 H。随后，第 2 处灰尘被移动到 $(6, 0)$。
• 在事件 7 中，Bitaro 计算第 4 处灰尘的坐标 $(3, 2)$。
• 在事件 8 中，Bitaro 使用宽度为 2 的扫帚执行过程 V。没有灰尘被移动。
• 在事件 9 中，Bitaro 计算第 3 处灰尘的坐标 $(3, 3)$。
• 在事件 10 中，Bitaro 计算第 2 处灰尘的坐标 $(6, 0)$。