Bitaro's room is an isosceles right-angled triangle whose leg has length ~N~. A point in Bitaro's room is represented as the coordinate ~(x, y)~ with ~0 \le x \le N~, ~0 \le y \le N~, ~x+y \le N~. The vertex of the right angle is the origin. The two legs of the triangle are the ~x~-axis and the ~y~-axis.

One day, Bitaro noticed that his room is full of dust. In the beginning, there are ~M~ dusts in the room. The ~i~-th dust ~(1 \le i \le M)~ lies in the point ~(X_i, Y_i)~. More than one dust may lie at the same point.

Now, Bitaro is planning to sweep the room using brooms. We consider a broom as a segment in the room and we call the length of the segment its width. Since Bitaro is well-organized, he can use a broom only in the following two ways.

• Bitaro puts the broom in the room so that one of its corners lies at the origin, and the broom is parallel to the ~y~-axis. Then, he moves the broom horizontally to the positive direction of the ~x~-axis as much as possible, keeping it parallel to the y-axis and one of its corners lying on the ~x~-axis. If the broom has width ~l~, a dust lying in ~(x, y)~ with ~x < N-l~ and ~y \le l~ will be moved to ~(N-l, y)~ (There may exist other dusts at ~(N-l, y)~). This is called the procedure ~H~.
• Bitaro puts the broom in the room so that one of its corners lies at the origin, and the broom is parallel to the ~x~-axis. Then, he moves the broom vertically to the positive direction of the ~y~-axis as much as possible, keeping it parallel to the ~x~-axis and one of its corners lying on the ~y~-axis. If the broom has width ~l~, a dust lying in ~(x, y)~ with ~x \le l~ and ~y < N-l~ will be moved to ~(x, N-l)~ (There may exist other dusts at ~(x, N-l)~). This is called the procedure ~V~.

In Bitaro's room, ~Q~ events will happen sequentially. The event ~j~ ~(1 \le j \le Q)~ is one of the following.

• Bitaro calculates the coordinates of the dust ~P_j~.
• Bitaro uses a broom with width ~L_j~ and performs the procedure ~H~.
• Bitaro uses a broom with width ~L_j~ and performs the procedure ~V~.
• A new dust is added at the point ~(A_j, B_j)~. If there are ~c~ dusts before this event, the new dust is the ~(c+1)~-th dust in the room.

Write a program which, given the length of the legs of the room, the coordinates of the dusts in the room, and the details of the events, calculates the coordinates of the dusts.

Input Specification

~N\ M\ Q~

~X_1\ Y_1~

~\dots~

~X_M\ Y_M~

~(Query\ 1)~

~\dots~

~(Query\ Q)~

Two or three space separated integers are written in each (~Query~ ~j~) ~(1 \le j \le Q)~. Let ~T_j~ be the first integer. Then the meaning of this line is as follows.

• If ~T_j = 1~, two integers ~T_j~, ~P_j~ are written in this line. This means, in the event ~j~, Bitaro calculates the coordinates of the dust ~P_j~.
• If ~T_j = 2~, two integers ~T_j~, ~L_j~ are written in this line. This means, in the event ~j~, Bitaro uses a broom with width ~L_j~ and performs the procedure ~H~.
• If ~T_j = 3~, two integers ~T_j~, ~L_j~ are written in this line. This means, in the event ~j~, Bitaro uses a broom with width ~L_j~ and performs the procedure ~V~.
• If ~T_j = 4~, three integers ~T_j~, ~A_j~, ~B_j~ are written in this line. This means, in the event ~j~, a new dust is added at the point ~(A_j, B_j)~.

Output Specification

For each event with ~T_j = 1~, write one line to the standard output. Output the ~x~-coordinate and the ~y~-coordinate of the dust ~P_j~ when the event ~j~ happens.

Constraints

~1 \le N \le 10^9~.

~1 \le M \le 5 \times 10^5~.

~1 \le Q \le 10^6~.

~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 \mathrm{(the\ number\ of\ dusts\ when\ the\ event\ } j \mathrm{\ happens)}~ ~(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)~.

There exists at least one event with ~T_j = 1~ ~(1 \le j \le Q)~.

Subtasks

1. (1 point) ~M \le 2 \times 10^3~, ~Q \le 5 \times 10^3~.
2. (10 points) ~T_j = 1, 2, 4~.
3. (11 points) ~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 points) ~T_j = 1, 2, 3~.
5. (25 points) No additional constraints.

Sample Input 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

Sample Output 1

1 3
3 2
3 3
6 0

Explanation for Sample 1

• In the beginning, the 1st dust lies at ~(1, 1)~, and the 2nd dust lies at ~(4, 0)~. Figure 1 describes the room.
• In the event 1, the 3rd dust is added at the point ~(2, 3)~. Figure 2 describes the room.
• In the event 2, Bitaro uses a broom with width 3 and performs the procedure ~V~. Then, the 1st dust is moved to ~(1, 3)~. Figure 3 describes the room.
• In the event 3, Bitaro calculates the coordinates ~(1, 3)~ of the 1st dust.
• In the event 4, the 4th dust is added at the point ~(1, 2)~. Figure 4 describes the room.
• In the event 5, Bitaro uses a broom with width 3 and performs the procedure ~H~. Then, the 1st dust is moved to ~(3, 3)~, the 3rd dust is moved to ~(3, 3)~, and the 4th dust is moved to ~(3, 2)~. Figure 5 describes the room.
• In the event 6, Bitaro uses a broom with width ~0~ and performs the procedure ~H~. Then, the 2nd dust is moved to ~(6, 0)~. Figure 6 describes the room.
• In the event 7, Bitaro calculates the coordinates ~(3, 2)~ of the 4th dust.
• In the event 8, Bitaro uses a broom with width 2 and performs the procedure ~V~. No dust is moved. Figure 7 describes the room.
• In the event 9, Bitaro calculates the coordinates ~(3, 3)~ of the 3rd dust.
• In the event 10, Bitaro calculates the coordinates ~(6, 0)~ of the 2nd dust.

This sample input satisfies the constraints of Subtasks 1 and 5.

Sample Input 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

Sample Output 2

3 6
4 3
7 1
6 3

Explanation for Sample 2

This sample input satisfies the constraints of Subtasks 1, 2, 4, and 5.

Sample Input 3

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

Sample Output 3

4 1
3 5
3 2

Explanation for Sample 3

This sample input satisfies the constraints of Subtasks 1, 2, and 5.

Sample Input 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

Sample Output 4

4 2
5 1
1 6
5 2

Explanation for Sample 4

This sample input satisfies the constraints of Subtasks 1, 3, 4, and 5.