Description

Since Bitaro got AK at IOI, the IOI organizers gave him a house. The room is an isosceles right triangle with leg length $N$. Any point in the room is represented by coordinates $(x,y)$, where $0\leq x+y\leq N$. The right-angle vertex is at the origin, and the two legs of the triangle are the $x$-axis and the $y$-axis.

One day, Bitaro found that he had already AK’ed $1919810$ IOIs, so he had nothing to do and decided to clean the dust in the room. Initially there are $M$ piles of dust, and the $i$-th pile is at $(X_i,Y_i)$. Also, it is possible that multiple piles of dust are at the same position.

Now Bitaro is going to sweep the room using a broom. We model the broom as a line segment placed in the room, and we call the length of this segment the broom’s width. Since Bitaro is very organized, he will only clean the room in the following two ways:

• Bitaro places the broom parallel to the $y$-axis, with one endpoint at the origin. Then he moves the broom to the right perpendicularly until it cannot move any further. If the broom’s width is $l$, then any dust pile originally at $(x,y)$ satisfying $x<N-l,y\leq l$ will be moved to $(N-l,y)$. (There may be multiple dust piles at this position.) We call this operation process H.

• Bitaro places the broom parallel to the $x$-axis, with one endpoint at the origin. Then he moves the broom upward horizontally until it cannot move any further. If the broom’s width is $l$, then any dust pile originally at $(x,y)$ satisfying $x\leq l,y<N-l$ will be moved to $(x,N-l)$. (There may be multiple dust piles at this position.) We call this operation process V.

In Bitaro’s room, there will be $Q$ events in order. The $i$-th event is one of the following four types:

• Bitaro wants to query the coordinates of the $P_i$-th dust pile.

• Bitaro uses a broom of width $L_i$ and performs process H.

• Bitaro uses a broom of width $L_i$ and performs process V.

• A new dust pile appears at point $(A_i,B_i)$. If there are $c$ dust piles in total before this event, then this new pile is the $(c+1)$-th dust pile in the room.

Since Bitaro has already AK’ed IOI and does not want to do anything, you need to write a program. Given the room’s leg length, the initial coordinates of each dust pile, and the details of each event, output the coordinates of the required dust piles.

Input Format

The first line contains three integers $N,M,Q$.

The next $m$ lines each contain two integers $X_i,Y_i$, representing the initial position of the $i$-th dust pile.

The next $Q$ lines each contain two or three integers, describing an event. Let $T_i$ be the first integer of the line. The meaning of each line is as follows:

• If $T_i=1$, then the line contains two integers $T_i,P_i$, meaning Bitaro queries the coordinates of the $P_i$-th dust pile.

• If $T_i=2$, then the line contains two integers $T_i,L_i$, meaning Bitaro performs process H using a broom of width $L_i$.

• If $T_i=3$, then the line contains two integers $T_i,L_i$, meaning Bitaro performs process V using a broom of width $L_i$.

• If $T_i=4$, then the line contains three integers $T_i,A_i,B_i$, meaning a new dust pile appears at position $(A_i,B_i)$.

Output Format

For each event with $T_i=1$, output one line with two integers, representing the coordinates of the $P_i$-th dust pile at the time event $i$ happens.

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

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

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

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

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

Hint

Sample 1 Explanation

At the beginning, the first dust pile is at $(1,1)$ and the second dust pile is at $(4,0)$. Figure 1 shows the current state of the room.

In the first event, the third dust pile is added at $(2,3)$. Figure 2 shows the current state of the room.

In the second event, Bitaro performs process V with a broom of width $3$. After that, the first dust pile moves to $(1,3)$. Figure 3 shows the current state of the room.

In the third event, Bitaro queries the coordinates of the first dust pile, which are $(1,3)$.

In the fourth event, the fourth dust pile is added at $(1,2)$. Figure 4 shows the current state of the room.

In the fifth event, Bitaro performs process H with a broom of width $3$. The first dust pile moves to $(3,3)$, the third dust pile moves to $(3,3)$, and the fourth dust pile moves to $(3,2)$. Figure 5 shows the current state of the room.

In the sixth event, Bitaro performs process H with a broom of width $0$. The second dust pile moves to $(6,0)$. Figure 6 shows the current state of the room.

In the seventh event, Bitaro queries the coordinates of the fourth dust pile, which are $(3,2)$.

In the eighth event, Bitaro performs process V with a broom of width $2$, but nothing happens. Figure 7 shows the current state of the room.

In the ninth event, Bitaro queries the coordinates of the third dust pile, which are $(3,3)$.

In the tenth event, Bitaro queries the coordinates of the second dust pile, which are $(6,0)$.

This sample satisfies the limits of Subtask 1 and Subtask 5.

Sample 2 to 5 Explanation

The second sample satisfies the limits of Subtask 1, 2, 4, and 5.

The third sample satisfies the limits of Subtask 1, 2, and 5.

The fourth sample satisfies the limits of Subtask 1, 3, 4, and 5.

The fifth sample satisfies the limits of Subtask 1 and Subtask 5.

Subtasks

For $100\%$ of the data, $1\leq n\leq 10^9,1\leq m\leq 5\times 10^5,1\leq Q\leq 10^6$. It is guaranteed that:

• $0\leq X_i,Y_i\leq N,X_i+Y_i\leq N(1\leq i\leq m)$.

• $1\leq P_i\leq M^\prime(1\leq i\leq Q)$, where $M^\prime$ is the number of dust piles at the time event $i$ happens.

• $0\leq L_i\leq n-1(1\leq i\leq Q)$.

• $0\leq A_i,B_i\leq n,A_i+B_i\leq n(1\leq i\leq Q)$.

• There is at least one event with $T_i=1$.

Translated by ChatGPT 5