Problem Description

There is an $N \times N$ matrix $ a $ that satisfies the following conditions:

• $a_{i,j} = N \times (i - 1) + j - 1$ ($1 \leq i,j \leq N$)

You are given $ Q $ queries $Query_{1}, \ldots, Query_{Q}$. Process them in order. There are 4 types of queries, and their input format and content are as follows:

• When $ Query_{i} = $ 1 A B: Swap the elements of the $ A $-th row and $ B $-th row of matrix $ a $ while maintaining the column numbers.
• When $ Query_{i} = $ 2 A B: Swap the elements of the $ A $-th column and $ B $-th column of matrix $ a $ while maintaining the row numbers.
• When $ Query_{i} = $ 3: Transpose the matrix. That is, the element $ a_{i,j} $ will be located at $ a_{j,i} $ after transposition.
• When $ Query_{i} = $ 4 A B: Output the element located at the $ A $-th row and $ B $-th column of matrix $ a $.

Note that for the 1st and 2nd types of queries, if $ A = B $, the matrix remains the same after processing the query.

Input Format

The input is given from the standard input in the following format:

$ N $ $ Q $ $ Query_{1} $ $ Query_{2} $ $\vdots$ $ Query_{Q} $

Output Format

For each query in the format 4 A B, output the answer as an integer, one per line, in the order the queries are given. Note that the answer may not fit into a 32-bit integer.

Sample Input and Output

Sample Input #1

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

Sample Output #1

0
1
2
3
0
2
1
3
1
3
0
2
3
1
2
0

Sample Input #2

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

Sample Output #2

1
6
8

Notes/Hints

Constraints

• All inputs are integers.
• $1 \leq N, Q \leq 10^{5}$
• $1 \leq A, B \leq N$
• There is at least one query in the format 4 A B.

Sample Explanation 1

In Sample Input #1, you can verify the values of each element of the matrix after each operation.

见题面 Input 部分

见题面 Output 部分