← 返回题目列表

AtCoder · past202005_i

I. 矩阵运算

中文机器翻译题面 查看原题

分数: 6 点

警告

2020 年 6 月 6 日下午 6:00 之前请勿提及此问题。日本标准时间。如有违反,可要求赔偿。 考试结束后,您可以向其他人透露您的总分和成绩,但仅此而已(例如,您解决了哪些问题)。

问题陈述

你有一个矩阵 a 尺寸 N \times N 满足以下条件:

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

你被给予 Q 查询。您的任务是按顺序处理它们。

每个查询 Query_{1}, Query_{2} \cdots Query_{Q} 由以下四种格式之一表示:

  • 1 A B : 交换所有元素 A第行和 B矩阵的第行 a 而不更改其列号。
  • 2 A B : 交换所有元素 A第列和 B矩阵的第列 a 而不更改其行号。
  • 3 :转置矩阵 a,即元素 a_{i,j} 将出现在 a_{j,i} 执行此查询后。
  • 4 A B : 输出元素 a_{i,j},即输出位于交集处的元素 A第行和 B矩阵的第列 a.

请注意矩阵 如果给定查询的格式为 a 将保持不变 1 A B or 2 A B 和 A=B.

约束

  • 输入中的所有值都是整数。
  • 1 \leq N, Q \leq 10^{5}
  • 1 \leq A, B \leq N
  • 保证至少有一个格式的查询 输入 4 A B 。

输入

输入由标准输入按以下格式给出:

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

输出

打印格式查询的答案 4 A B 按照它们在输入中出现的顺序排列。

请注意,答案可能不适合 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,可以查看矩阵的所有元素 a 执行每种类型的查询后。


示例输入 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