시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
11 초 2048 MB 0 0 0 0.000%

문제

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 ≤ x ≤ N, 0 ≤ y ≤ N, x + y ≤ 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 ≤ i ≤ M) lies in the point (Xi, Yi). 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 ≤ 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 ≤ 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 ≤ j ≤ Q) is one of the following.

  • Bitaro calculates the coordinates of the dust Pj.
  • Bitaro uses a broom with width Lj and performs the procedure H.
  • Bitaro uses a broom with width Lj and performs the procedure V.
  • A new dust is added at the point (Aj, Bj). 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.

입력

Read the following data from the standard input. All the values in the input are integers.

N M Q
X1 Y1
.
.
.
XM YM
(Query 1)
.
.
.
(Query Q)

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

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

출력

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

제한

  • 1 ≤ N ≤ 1 000 000 000.
  • 1 ≤ M ≤ 500 000.
  • 1 ≤ Q ≤ 1 000 000.
  • 0 ≤ Xi ≤ N (1 ≤ i ≤ M).
  • 0 ≤ Yi ≤ N (1 ≤ i ≤ M).
  • Xi + Yi ≤ N (1 ≤ i ≤ M).
  • 1 ≤ Pj ≤ (the number of dusts when the event j happens) (1 ≤ j ≤ Q).
  • 0 ≤ Lj ≤ N − 1 (1 ≤ j ≤ Q).
  • 0 ≤ Aj ≤ N (1 ≤ j ≤ Q).
  • 0 ≤ Bj ≤ N (1 ≤ j ≤ Q).
  • Aj + Bj ≤ N (1 ≤ j ≤ Q).
  • There exists at least one event with Tj = 1 (1 ≤ j ≤ Q).

예제 입력 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
  • 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.
Figure 1 Figure 2
Figure 3 Figure 4
Figure 5 Figure 6
 
Figure 7  

예제 입력 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

예제 출력 2

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

예제 출력 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

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

예제 출력 5

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