Problem Statement

Takahashi is conducting an experiment by rolling \(N\) dice on a line of squares.

The squares are arranged in a row, numbered \(1\) through \(M\). The square numbers are assigned sequentially from one end as \(1,2,\dots,M\).

Each die \(i\) (\(1 \leq i \leq N\)) is initially placed on square \(S_i\). Multiple dice may be placed on the same square, but the dice do not affect each other and are treated independently.

Each die is a standard six-sided die, with numbers \(1\) through \(6\) written on its six faces, one per face. The sum of the numbers on opposite faces is always \(7\).

In this problem, the orientation of a die is represented by a pair of the top face number and the front face number. The front face is the face facing in the direction of increasing square numbers.

In the initial state of die \(i\), the top face number is \(U_i\) and the front face number is \(F_i\). Since the top and front faces are neither the same face nor opposite faces, it is guaranteed that \(U_i \neq F_i\) and \(U_i+F_i \neq 7\).

Takahashi performs \(Q\) operations in order. In the \(j\)-th operation (\(1 \leq j \leq Q\)), he rolls die \(d_j\) by \(1\) square in direction \(c_j\) (+ or -).

When rolling a die, let \(u\) be the top face number and \(f\) be the front face number immediately before the roll. The position and orientation change according to the following rules:

• Rolling in the + direction (direction of increasing square numbers):
• The position increases by \(1\).
• The new top face number becomes \(7-f\), and the new front face number becomes \(u\).
• This corresponds to a rotation where the face that was the front becomes the bottom, the face that was the back becomes the top, and the face that was the top becomes the front.

• Rolling in the - direction (direction of decreasing square numbers):
• The position decreases by \(1\).
• The new top face number becomes \(f\), and the new front face number becomes \(7-u\).
• This corresponds to the reverse rotation of the + direction: the face that was the back becomes the bottom, the face that was the front becomes the top, and the face that was the top becomes the back.

It is guaranteed that throughout all operations, the position of each die remains within the range of \(1\) to \(M\), inclusive.

After completing all \(Q\) operations, find the final position and top face number for each die. You do not need to output the front face number.

Constraints

• \(1 \leq N \leq 2\times 10^5\)
• \(1 \leq M \leq 10^9\)
• \(1 \leq Q \leq 2\times 10^5\)
• \(N+Q \leq 2\times 10^5\)
• \(1 \leq S_i \leq M\) (\(1 \leq i \leq N\))
• \(1 \leq U_i \leq 6\) (\(1 \leq i \leq N\))
• \(1 \leq F_i \leq 6\) (\(1 \leq i \leq N\))
• \(U_i \neq F_i\) and \(U_i+F_i \neq 7\) (\(1 \leq i \leq N\))
• \(1 \leq d_j \leq N\) (\(1 \leq j \leq Q\))
• \(c_j\) is + or - (\(1 \leq j \leq Q\))
• As a result of operations, the position of any die will never be less than \(1\) or exceed \(M\).
• All input values except \(c_j\) are integers.

Sample Input 1

1 5 3
2 1 2
1 +
1 +
1 -

Sample Output 1

3 5

Sample Input 2

3 6 7
1 1 2
6 6 5
3 3 1
1 +
2 -
3 -
3 +
1 +
2 +
1 -

Sample Output 2

2 5
6 6
3 3

Sample Input 3

5 20 15
1 1 3
20 2 4
10 3 2
5 4 1
15 5 3
1 +
2 -
3 +
4 -
5 +
1 +
3 +
2 -
5 -
4 +
1 -
3 -
2 +
5 +
4 -

Sample Output 3

2 4
19 4
11 5
4 1
16 4

Sample Input 4

10 1000000000 36
1 1 2
1000000000 6 4
500000000 2 3
999999999 3 1
123456789 4 5
987654321 5 1
2 1 3
999999998 2 4
400000000 3 6
600000000 6 2
1 +
2 -
7 -
8 +
4 +
3 +
5 -
6 +
9 +
10 -
1 -
2 +
7 +
8 +
4 -
3 +
5 +
6 -
9 -
10 +
1 +
2 -
7 -
8 -
4 +
3 -
5 -
6 +
9 +
10 -
1 +
2 -
7 +
8 +
4 -
3 +

Sample Output 4

3 6
999999998 1
500000002 5
999999999 3
123456788 5
987654322 6
2 1
1000000000 5
400000001 1
599999999 2

Sample Input 5

1 2 15
1 1 2
1 +
1 -
1 +
1 -
1 +
1 -
1 +
1 -
1 +
1 -
1 +
1 -
1 +
1 -
1 +

Sample Output 5

2 5