I - Matrix Operations Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 6 点

注意

この問題に対する言及は、2020/6/6 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。 試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。

問題文

以下の条件を満たすような N \times N 行列 a があります。

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

Q 個のクエリ Query_{1}, \ldots, Query_{Q} が与えられるので、順番に処理してください。 クエリは 4 種類あり、入力形式とクエリの内容は以下の通りです。

  • Query_{i} = 1 A B のとき: 行列 a の A 行目と B 行目の要素を列番号を維持しながら交換せよ。
  • Query_{i} =2 A B のとき: 行列 a の A 列目と B 列目の要素を行番号を維持しながら交換せよ。
  • Query_{i} =3 のとき: 行列を転置せよ。つまり a_{i,j} の要素は転置後 a_{j,i} に位置する。
  • Query_{i} =4 A B のとき: 行列 a の A 行 B 列に位置する要素を出力せよ。

ただし、1 番目と 2 番目の種類のクエリにおいて A=B であったとき、クエリを処理したあとの行列は処理する前と同じであることに注意してください。

制約

  • 入力は全て整数
  • 1 \leq N, Q \leq 10^{5}
  • 1 \leq A, B \leq N
  • 4 A B という形式のクエリが 1 つ以上存在する

入力

入力は以下の形式で標準入力から与えられる。

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

出力

4 A B という形式のクエリに対する答えを、クエリが与えられた順にそれぞれ 1 行ずつ整数で出力せよ。 答えは 32 ビット整数に収まらない可能性があることに注意せよ。

入力例 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

出力例 1

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

入力例 1 では、各操作後の行列のそれぞれの要素の値を確かめることができます。

入力例 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

出力例 2

1
6
8

Score : 6 points

Warning

Do not make any mention of this problem until June 6, 2020, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

You have a matrix a of size N \times N satisfying the following condition:

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

You are given Q queries. Your task is to process them sequentially.

Each query Query_{1}, Query_{2} \cdots Query_{Q} is represented by one of the following four types of format:

  • 1 A B : Swap all the elements of the A-th row and the B-th row of the matrix a without changing their column numbers.
  • 2 A B : Swap all the elements of the A-th column and the B-th column of the matrix a without changing their row numbers.
  • 3 : Transpose the matrix a, i.e. the element of a_{i,j} will appear at a_{j,i} after performing this query.
  • 4 A B : Output the element of a_{i,j}, i.e. output the element located at the intersection of the A-th row and the B-th column of the matrix a.

Note that the matrix a will remain the same if the given queries are of format either 1 A B or 2 A B and A=B.

Constraints

  • All the values in the input are integers.
  • 1 \leq N, Q \leq 10^{5}
  • 1 \leq A, B \leq N
  • It is guaranteed that there is at least one query of format 4 A B in the input.

Input

Input is given from Standard Input in the following format:

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

Output

Print answers to the queries of the format 4 A B in the order they appear in the input.

Be careful that the answers might not fit in the 32-bit data type.

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

In the sample 1, you can check all the elements of the matrix a after performing each type of query.

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