청소

비타로의 방은 다리의 길이가 $N$인 직각이등변삼각형이다. 방 안의 점은 좌표 $(x, y)$로 나타내며, $0 \le x \le N$, $0 \le y \le N$, $x + y \le N$을 만족한다. 직각의 꼭짓점은 원점이고, 두 다리는 x축과 y축이다.

어느 날 비타로는 방에 먼지가 가득한 것을 발견했다. 처음에 방에는 $M$개의 먼지가 있다. $i$번째 먼지($1 \le i \le M$)는 점 $(X_i, Y_i)$에 있다. 같은 점에 먼지가 여러 개 있을 수 있다.

비타로는 빗자루로 방을 쓴다. 빗자루는 방 안의 선분이며, 선분의 길이를 빗자루의 너비라고 부른다. 비타로는 다음 두 절차로만 빗자루를 사용한다.

1. 절차 H: 빗자루의 한쪽 끝을 원점에 두고 y축과 평행하게 놓는다. 한쪽 끝을 x축 위에 둔 채 y축과 평행을 유지하면서, 빗자루를 x축의 양의 방향으로 최대한 민다. 너비가 $l$이면, $x < N - l$이고 $y \le l$인 점 $(x, y)$의 먼지는 $(N - l, y)$로 옮겨진다. $(N - l, y)$에는 다른 먼지가 있을 수 있다.
2. 절차 V: 빗자루의 한쪽 끝을 원점에 두고 x축과 평행하게 놓는다. 한쪽 끝을 y축 위에 둔 채 x축과 평행을 유지하면서, 빗자루를 y축의 양의 방향으로 최대한 민다. 너비가 $l$이면, $x \le l$이고 $y < N - l$인 점 $(x, y)$의 먼지는 $(x, N - l)$로 옮겨진다. $(x, N - l)$에는 다른 먼지가 있을 수 있다.

방에서는 Q개의 이벤트가 순서대로 일어난다. 이벤트 $j$($1 \le j \le Q$)는 다음 중 하나이다.

• 비타로가 먼지 $P_j$의 좌표를 계산한다.
• 비타로가 너비 $L_j$의 빗자루로 절차 H를 수행한다.
• 비타로가 너비 $L_j$의 빗자루로 절차 V를 수행한다.
• 점 $(A_j, B_j)$에 새 먼지가 추가된다. 이벤트 전에 먼지가 $c$개 있었다면, 새 먼지는 방의 $(c + 1)$번째 먼지가 된다.

다리의 길이, 먼지의 좌표, 이벤트가 주어졌을 때 먼지의 좌표를 구하는 프로그램을 작성하시오.

N M Q
X_1 Y_1
.
.
.
X_M Y_M
(질의 1)
.
.
.
(질의 Q)

각 질의 줄에는 두 개 또는 세 개의 정수가 있다. 첫 번째 정수를 $T_j$라고 한다.

• $T_j = 1$이면 줄에 $T_j$와 $P_j$가 있다. 이벤트 $j$에서 비타로는 먼지 $P_j$의 좌표를 계산한다.
• $T_j = 2$이면 줄에 $T_j$와 $L_j$가 있다. 이벤트 $j$에서 비타로는 너비 $L_j$의 빗자루로 절차 H를 수행한다.
• $T_j = 3$이면 줄에 $T_j$와 $L_j$가 있다. 이벤트 $j$에서 비타로는 너비 $L_j$의 빗자루로 절차 V를 수행한다.
• $T_j = 4$이면 줄에 $T_j$, $A_j$, $B_j$가 있다. 이벤트 $j$에서 점 $(A_j, B_j)$에 새 먼지가 추가된다.

$T_j = 1$인 각 이벤트마다 이벤트 시점의 먼지 $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$, $0 \le Y_i \le N$, $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$, $0 \le B_j \le N$, $A_j + B_j \le N$ ($1 \le j \le Q$)
• $T_j = 1$인 이벤트가 적어도 하나 있다.
• 시간 제한은 11000 ms, 메모리 제한은 2048 MB이다.