题目描述

请你维护 $n$ 个大小为 $m$ 的方阵。初始时每个方阵 $W$ 用两个参数 $A_i,B_i$ 表示，其中 $W_{i,j}=(iA+jB)\bmod m$（$0\le i,j<m$）。保证 $1\le A,B<m$，且 $m$ 为质数。

注意：本题中方阵元素下标从 $\bf0$ 开始，但方阵按 $\bf{1\dots n}$ 编号。

我们定义对一个长度为 $m$、值域 $[0,m)$ 的序列 $a$ 的函数 $f(a)=b$，其中 $b$ 也是一个长度为 $m$、值域 $[0,m)$ 的序列。对于 $[0,m)$ 的所有 $i$，若 $i$ 在 $a$ 中出现至少 $1$ 次，则 $b_i$ 为 $i$ 第一次出现的位置；否则 $b_i$ 为 $i$。

我们对这些方阵进行一些操作和询问，具体如下：

• 操作 1 l r x y：将第 $l$ 到 $r$ 的所有方阵向上平移 $x$ 次，向左平移 $y$ 次。形式化地，得到的新方阵中 $W'_{i,j}=W_{(i+x)\bmod m,(j+y)\bmod m}$。
• 操作 2 l r：将第 $l$ 到 $r$ 的所有方阵的每一行（一个序列 $a$）变成 $f(a)$。
• 操作 3 l r：将第 $l$ 到 $r$ 的所有方阵的每一列（一个序列 $a$）变成 $f(a)$。
• 询问 4 l x y：询问第 $l$ 个方阵的 $W_{x,y}$ 的值是多少。

这题正解有点太奇怪又太典了，所以部分分很多。

输入格式

第一行输入三个正整数 $n,m,q$。$q$ 表示询问次数。

第二行 $n$ 个正整数 $A_i$。

第三行 $n$ 个正整数 $B_i$。

后 $q$ 行每行三到五个个整数，格式见题目描述。

输出格式

对于每次询问，输出一个非负整数表示答案。容易发现答案 $\in[0,m)$。

5 3 31
1 1 1 1 1
1 1 1 1 1
1 1 1 2 2
1 2 2 1 1
2 3 3
3 4 4
1 5 5 2 1
2 5 5
3 5 5
1 5 5 1 2
3 5 5
2 5 5
1 5 5 2 1
2 5 5
3 5 5
1 5 5 1 2
3 5 5
2 5 5
4 1 0 0
4 1 1 1
4 1 2 2
4 2 0 0
4 2 1 1
4 2 2 2
4 3 0 0
4 3 1 1
4 3 2 2
4 4 0 0
4 4 1 1
4 4 2 2
4 5 0 0
4 5 1 1
4 5 2 2

1
0
2
2
1
0
0
0
0
0
0
0
1
0
2

10 11 50
10 4 2 8 1 8 5 10 6 5 
3 4 4 1 1 5 6 6 5 10 
4 5 2 4
1 2 6 1 6
1 7 8 5 0
4 9 9 6
4 2 2 9
1 10 10 5 5
1 1 5 4 0
1 3 4 3 9
1 2 3 9 7
1 1 9 0 10
1 10 10 9 1
1 2 10 6 2
4 7 2 0
4 6 2 6
1 2 3 5 10
4 5 4 7
4 9 7 1
4 5 0 8
1 4 7 8 2
4 3 6 1
1 7 7 2 5
1 4 4 4 9
4 9 9 0
1 3 6 4 7
1 1 9 7 6
4 5 2 7
4 3 5 0
4 9 5 3
1 7 9 7 2
4 5 6 0
1 1 7 7 1
1 2 5 5 10
1 2 5 3 8
1 3 4 0 6
1 2 4 10 9
1 1 9 9 4
4 1 0 0
1 4 5 6 2
4 5 2 2
1 2 5 9 2
4 1 9 7
1 5 9 0 3
4 8 1 2
1 9 10 6 1
4 5 1 8
1 8 10 1 9
1 2 5 0 8
1 6 6 9 10
1 1 9 4 6
4 2 0 2

6
7
6
5
5
7
0
4
6
7
6
8
4
3
3
1
4
7
9
9

提示

样例解释 1

最后五个方阵形如：

$$\left[\begin{matrix}1&2&0\\2&0&1\\0&1&2\end{matrix}\right]\left[\begin{matrix}2&0&1\\0&1&2\\1&2&0\end{matrix}\right]\left[\begin{matrix}0&1&2\\2&0&1\\1&2&0\end{matrix}\right]\left[\begin{matrix}0&2&1\\1&0&2\\2&1&0\end{matrix}\right]\left[\begin{matrix}1&2&0\\2&0&1\\0&1&2\end{matrix}\right] $$

数据范围

$1\le n\le 2\cdot 10^5$，$1\le q\le 10^5$。$2\le m\le 2933256077$，且 $m$ 为质数。$1\le A,B<m$。若其中有 $q_0$ 次操作，$q-q_0$ 次询问，则 $0\le q_0<\min(40001,q)$。

操作 $1$ 中 $0\le x,y<m$。

• Subtask 1：$n,m,q\le 100$，$20$ 分。
• Subtask 2：$n,m,q\le 500$，$A_i=B_i=1$。$10$ 分。
• Subtask 3：$n,m,q\le 5000$。没有 $2,3$ 操作。$10$ 分。
• Subtask 4：$m\le 3000$，没有 $1,3$ 操作。所有 $A_i$ 相等，所有 $B_i$ 相等。$25$ 分。
• Subtask 5：$n,q\le5000$，$A_i=B_i=1$。$15$ 分。
• Subtask 6：$l_i=1$，$r_i=n$。$10$ 分。
• Subtask 7：无特殊性质。$10$ 分。