Problem Description

Since Bitaro has aced the IOI, the IOI organizers have gifted him a house, which is an isosceles right triangle with a side length of \( N \). A point inside the room is represented by coordinates \((x, y)\), where \( 0 \leq x + y \leq N \). The right-angled vertex is the origin, and the two legs of the triangle are the \( x \)-axis and \( y \)-axis.

One day, Bitaro found himself with nothing to do after acing the 1919810th IOI and decided to clean the dust in his room. Initially, there are \( M \) piles of dust, with the \( i \)-th pile located at \((X_i, Y_i)\). Multiple piles of dust can be at the same location.

Bitaro plans to use a broom to clean the room. The broom is placed as a line segment in the room, and its length is referred to as its width. Bitaro will only clean the room using the following two methods:

• Bitaro places the broom parallel to the \( y \)-axis, with one end at the origin. He then moves the broom vertically to the right until it can't move anymore. If the broom's width is \( l \), then any pile of dust satisfying \( x < N - l, y \leq l \) will be moved to \((N - l, y)\). This process is called Process H.

• Bitaro places the broom parallel to the \( x \)-axis, with one end at the origin. He then moves the broom horizontally upwards until it can't move anymore. If the broom's width is \( l \), then any pile of dust satisfying \( x \leq l, y < N - l \) will be moved to \((x, N - l)\). This process is called Process V.

In Bitaro's room, \( Q \) events will occur in sequence. The \( i \)-th event can be one of the following four types:

• Bitaro wants to calculate the coordinates of the \( P_i \)-th pile of dust;
• Bitaro uses a broom with width \( L_i \) and performs Process H;
• Bitaro uses a broom with width \( L_i \) and performs Process V;
• A new pile of dust appears at point \((A_i, B_i)\). If there were \( c \) piles of dust before this event, this new pile is the \( c+1 \)-th pile.

Since Bitaro has aced the IOI and doesn't want to do anything, you need to write a program that, given the side length of the room, the initial positions of the dust piles, and the details of each event, calculates the coordinates of the required dust pile.

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 pile of dust.

The next \( Q \) lines each describe an event. Let \( T_i \) be the first integer of each line, with the following meanings:

• If \( T_i = 1 \), the line contains two integers \( T_i, P_i \), indicating Bitaro wants to calculate the coordinates of the \( P_i \)-th pile of dust;
• If \( T_i = 2 \), the line contains two integers \( T_i, L_i \), indicating Bitaro uses a broom with width \( L_i \) to perform Process H;
• If \( T_i = 3 \), the line contains two integers \( T_i, L_i \), indicating Bitaro uses a broom with width \( L_i \) to perform Process V;
• If \( T_i = 4 \), the line contains three integers \( T_i, A_i, B_i \), indicating a new pile of dust appears at \((A_i, B_i)\).

Output Format

For each event where \( T_i = 1 \), output a line containing two integers, representing the coordinates of the \( P_i \)-th pile of dust at the time of event \( i \).

Sample Input and Output

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

Output Sample #1

1 3
3 2
3 3
6 0

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

Output Sample #2

3 6
4 3
7 1
6 3

Input Sample #3

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

Output Sample #3

4 1
3 5
3 2

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

Output Sample #4

4 2
5 1
1 6
5 2

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

Output Sample #5

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

Notes/Hints

Sample 1 Explanation

Initially, the first pile of dust is at \((1,1)\) and the second pile is at \((4,0)\). Figure 1 describes the current state of the room.

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

In the second event, Bitaro uses a broom with width \(3\) to perform Process V. The first pile of dust moves to \((1,3)\). Figure 3 describes the current state of the room.

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

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

In the fifth event, Bitaro uses a broom with width \(3\) to perform Process H. The first pile of dust moves to \((3,3)\), the third pile of dust moves to \((3,3)\), and the fourth pile of dust moves to \((3,2)\). Figure 5 describes the current state of the room.

In the sixth event, Bitaro uses a broom with width \(0\) to perform Process H. The second pile of dust moves to \((6,0)\). Figure 6 describes the current state of the room.

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

In the eighth event, Bitaro uses a broom with width \(2\) to perform Process V, but nothing happens. Figure 7 describes the current state of the room.

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

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

This sample satisfies the constraints of Subtasks 1 and 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 \). The following guarantees are provided:

• \( 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' (1 \leq i \leq Q) \), where \( M' \) is the number of dust piles at the time of event \( i \);
• \( 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 where \( T_i = 1 \).

见题面 Input 部分

见题面 Output 部分