You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

时空限制

2S/512M

题目描述

有 $n\times m$ 个同学排成 $n$ 行 $m$ 列的方阵。初始时，第 $i$ 行第 $j$ 列的同学编号为 $(i-1)\times m+j$。

有 $q$ 条训练指令，指令分为以下三种：

• $1\ x\ y$，表示让第 $x$ 行的每个同学与第 $y$ 行同列的同学交换位置；
• $2\ x\ y$，表示让第 $x$ 列的每个同学与第 $y$ 列同行的同学交换位置；
• $3\ x\ y$，表示询问此时第 $x$ 行第 $y$ 列的同学编号。

格式

输入格式

第一行包含三个整数 $n,m,q$，分别表示方阵的行数和列数以及训练指令的数量。

接下来 $q$ 行每行一条训练指令，格式见题目描述。

输出格式

对于每条 $3$ 类的询问，在单独的一行中输出一个整数表示答案。

样例

样例输入 #1

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

样例输出 #1

3
1

样例解释 #1

初始时方阵中同学的编号情况如下：

第 $1$ 条指令执行后方阵中同学的编号情况如下：

第 $2$ 条指令执行后方阵中同学的编号情况如下：

此时第 $2$ 行第 $2$ 列的同学编号为 $3$。

第 $4$ 条指令执行后方阵中同学的编号情况如下：

第 $5$ 条指令执行后方阵中同学的编号情况如下：

此时第 $3$ 行第 $4$ 列的同学编号为 $1$。

数据规模

对于 $40\%$ 的数据，$n,m\leq 2000$，$q\leq 2000$。

另有 $20\%$ 的数据，不存在 $2$ 类指令。

对于 $100\%$ 的数据，$1\leq n,m\leq 10^6$，$1\leq q\leq 10^6$。数据保证：对于 $1$ 类指令，$1\leq x<y\leq n$；对于 $2$ 类指令，$1\leq x<y\leq m$；对于 $3$ 类指令，$1\leq x\leq n$，$1\leq y\leq m$。