题目描述

给定序列 $a_{1\cdots n}$ 与常数 $m$，你需要维护并支持 $q$ 次以下操作：

• 1 l r a b，添加一条 $x\gets (ax+b)\bmod m$ 且针对 $a_{l\cdots r}$ 的变换到计划中，即若执行这条计划，对于 $l\leq i\leq r$，$a_i\gets (a\times a_i+b)\bmod m$；
• 2 l r k，询问若执行计划中第 $[l,r]$ 条变换，$a_k$ 的值会是多少。

注意询问独立，即不会对 $a$ 序列实际做出修改。

输入格式

第一行一个整数 $type$ 表示这组数据的 特征值，它是一个 $0\sim 31$ 之间的整数，你需要将其转换为一个五位的二进制数，最低位为第一位，其意义如下：

如果第一位为 $1$，代表数据进行了加密，否则数据没有进行加密。对于已加密的数据，你需要把第一种操作中的 $l,r$ 以及第二种操作中的 $l,r,k$ 与上一次询问操作得到的答案 $lastans$ 进行异或操作来得到正确的操作信息。$lastans$ 初始值视为 $0$。

如果第二位为 $1$，代表修改操作会出现 $(0x+b)\bmod m$（$b$ 不为 $0$）的形式，否则一定不会出现这样的修改。

如果第三位为 $1$，代表修改操作会出现 $(ax+0)\bmod m$（$a$ 不为 $0$）的形式，否则一定不会出现这样的修改。

如果第四位为 $1$，代表修改操作会出现 $(ax+b)\bmod m$（$a,b$ 均不为 $0$）的形式，否则一定不会出现这样的修改。

如果第五位为 $1$，则我们保证给出的 $m$ 是一个质数，否则不保证。

第二行两个整数 $n,m$。

第三行 $n$ 个整数依次表示 $a_{1\cdots n}$。

第四行一个整数 $q$ 表示操作次数。

接下来 $q$ 行，每行一个操作，格式见题目描述。

输出格式

对每个第 $2$ 类操作，输出独占一行的一个整数，表示那次询问的结果。

24
3 5
1 2 3
5
1 1 2 3 2
1 2 3 4 3
2 1 1 3
1 1 3 1 4
2 1 3 2

3
4

7
3 5
1 2 3
5
1 1 2 0 3
1 2 3 4 0
2 1 1 3
1 2 0 2 0
2 2 0 1

3
4

数据规模与约定

对于 $100\%$ 的数据，$1\leq n\leq 10^5$，$1\leq q\leq 6\times 10^5$。

我们保证，同类型的测试点中加密与不加密的数据点各占 $50\%$，且修改操作数不超过 $10^5$，所有数的都可以用 int 存下。

由于本题数据量较大，请自行使用读入优化；由于测试点较多以及时限较长，为了大家的正常做题，请尽量减少提交本题的次数。

来源

$2015$ 年国家集训队测试。