F. Permutation Grid
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

A left circular shift of a sequence moves its first element to the end. For example, the sequence $$$[1, 2, 3, 4]$$$ becomes $$$[2, 3, 4, 1]$$$ after applying a circular shift.

We can construct a grid $$$g$$$ of size $$$n$$$ by $$$n$$$ as follows: The first row of $$$g$$$ is $$$[1, 2, ..., n]$$$. For $$$i = 2$$$ to $$$n$$$, row $$$i$$$ is obtained by applying a left circular shift to row $$$i - 1$$$.

For example, when $$$n = 4$$$ our grid is: 


1 2 3 4
2 3 4 1
3 4 1 2
4 1 2 3

You need to process $$$q$$$ queries of the following four types:

R x k: Apply a left circular shift on row $$$x$$$ by $$$k$$$ positions if row $$$x$$$ is a circular shift of $$$[1, 2, ..., n]$$$.

C x k: Apply an upward circular shift on column $$$x$$$ by $$$k$$$ positions if column $$$x$$$ is a circular shift of $$$[1, 2, ..., n]$$$.

S x y: Swap rows $$$x$$$ and $$$y$$$

Q x y: Output the value currently in row $$$x$$$, column $$$y$$$

Input

The first line contains two integers $$$n$$$ and $$$q$$$, $$$(1 \leq n, q \leq 2 \cdot 10^5)$$$.

The next $$$q$$$ lines describe the queries, with format as stated in the problem statement.

Output

For each query of type $$$Q$$$, output the value in the corresponding location.

Scoring
SubtaskConstraintPoints
$$$1$$$$$$n, q \leq 1000$$$$$$30$$$
$$$2$$$There is no query of types S$$$30$$$
$$$3$$$The corresponding row / column will be a circular shift in queries of type R and C$$$30$$$
$$$4$$$No additional constraints$$$60$$$
Example
Input
4 7
R 1 1
R 2 3
Q 2 3
C 3 1
S 1 2
C 1 2
Q 4 1
Output
3
2
Note

After the first two queries, the grid becomes


2 3 4 1
1 2 3 4
3 4 1 2
4 1 2 3

For the third query, the number in row $$$2$$$, column $$$3$$$ is $$$3$$$.

Then, in the fourth query, since the third column isn't a circular shift of $$$[1, 2, \dots, n]$$$, nothing happens.

The fifth query swaps the first and second rows, making the grid identical to where it started.

The sixth query performs a circular shift on column $$$1$$$, resulting in the grid


3 2 3 4
4 3 4 1
1 4 1 2
2 1 2 3

For the seventh query, the number in row $$$4$$$, column $$$1$$$ is $$$2$$$.