You are given a grid of $N$ integers, where $N$ is a power of two. Rows and columns are numbered starting at $1$ from top to bottom and left to right, respectively.

The grid initially consists of a single row containing the integers from $1$ to $N$, in order. You are to handle $Q$ updates and queries on the grid:

1. X 0 - Cut the grid into left and right halves and put the left half on top of the right half.
2. X 1 - Cut the grid into left and right halves and put the right half on top of the left half.
3. Y 0 - Cut the grid into top and bottom halves and put the top half on the left of the bottom half.
4. Y 1 - Cut the grid into top and bottom halves and put the bottom half on the left of the top half.
5. Q x - Determine the current row and column number of the value $x$.

For all of the cut operations, it is guaranteed that there will be at least two rows/columns in the direction which must be cut in half. Rows and columns are renumbered starting at $1$ from top to bottom and left to right after each cut.

Constraints

$2\le N\le 2^{30}$

$1\le Q\le 5\times {10}^5$

$1\le x\le N$

$N$ is a power of two.

Subtask $\frac{1}{\phantom{2}}$ [1/2 points]

$x=1$

Subtask $\frac{\phantom{1}}{2}$ [1/2 points]

No additional constraints.

Input Specification

The first line contains two space-separated integers, $N$ and $Q$, the number of integers in the grid and the number of updates and queries, respectively.

The next $Q$ lines each contain a query or update in one of the following formats:

1. X 0 - Cut the grid into left and right halves and put the left half on top of the right half.
2. X 1 - Cut the grid into left and right halves and put the right half on top of the left half.
3. Y 0 - Cut the grid into top and bottom halves and put the top half on the left of the bottom half.
4. Y 1 - Cut the grid into top and bottom halves and put the bottom half on the left of the top half.
5. Q x - Determine the current row and column number of the value $x$.

For all of the cut operations, it is guarenteed that there will be at least two rows/columns in the direction which must be cut in half.

Output Specification

For every query operation (type Q), output a line containing two space-separated integers, the current row and column number of the queried value.

Sample Input

8 9
Q 3
X 0
X 1
Q 1
Y 0
Q 8
Q 7
Y 1
Q 4

Sample Output

1 3
3 1
2 2
2 1
1 6

Explanation for Sample

The grid initially looks like this:

1 2 3 4 5 6 7 8

The first operation, Q 3, queries the current position of the value $3$, which is row $1$, column $3$. Thus, the correct output for this query is 1 3.

The second operation, X 0, cuts the grid into left and right halves and puts the left half on top of the right half:

1 2 3 4
5 6 7 8

The third operation, X 1, cuts the grid into left and right halves and puts the right half on top of the left half:

3 4
7 8
1 2
5 6

The fourth operation, Q 1, queries the current position of the value $1$, which is row $3$, column $1$. Thus, the correct output for this query is 3 1.

The fifth operation, Y 0, cuts the grid into top and bottom halves and puts the top half on the left of the bottom half:

3 4 1 2
7 8 5 6

The sixth operation, Q 8, queries the current position of the value $8$, which is row $2$, column $2$. Thus, the correct output for this query is 2 2.

The seventh operation, Q 7, queries the current position of the vallue $7$, which is row $2$, column $1$. Thus, the correct output for this query is 2 1.

The eighth operation, Y 1, cuts the grid into top and bottom halves and puts the bottom half on the left of the top half:

7 8 5 6 3 4 1 2

The ninth operation, Q 4, queries the current position of the value $4$, which is row $1$, column $6$. Thus, the correct output for this query is 1 6.