巨酱有 $n$ 副耳机，他把它们摆成了一列，并且由 $1$ 到n依次编号。每个耳机有一个玄学值，反映了各自的一些不可名状的独特性能。玄学值都是 $0$ 到 $m-1$ 间的整数。在外界的作用下（包括但不限于换线、上放、更换电源为核电、让kAc叔叔给它们讲故事），这些耳机的玄学值会发生改变。特别地，巨酱观察发现，每种作用 $o$ 对应了两个整数 $a_o$与 $b_o$，在这种作用之后，玄学值原本为 $x$ 的耳机，其玄学值恰会变成 $(a_{o}x+b_o)modm$。

巨酱对他手头耳机的表现并不满意，遗憾的是，最近他并不有钱，无法任性，不能赶紧买买买以满足自己。手头紧张的他准备拟定一个相对经济的方案，通过各种作用来改善他手头玩具的性能。具体地说，为了尽快完成方案的制订，巨酱希望自己能高效地完成以下工作：

1. 巨酱想到了一种操作，能让耳机的玄学值由 $x$ 变为 $(ax+b)modm$，并且他计划对编号为 $i$ 到 $j$ 的耳机执行这种操作。
2. 巨酱想知道如果将（并且仅将）自己的第 $i$ 个到第 $j$ 个计划按顺序付诸行动，编号为 $k$ 的耳机的玄学值将会变成多少。

出于著名算法竞赛选手的矜持，巨酱表示自己才不需要你的帮助。但是如果巨酱真的厌倦了自己的玩具，它们就会被50包邮出给主席。为了不让后者白白捡到便宜，你考虑再三还是决定出手。

输入格式

第 1 行只有一个整数，表示本组测试数据的特征。特征值为一个 $0\sim 31$ 的整数。我们把这个整数转换成一个五位的二进制数，最低位为第一位。

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

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

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

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

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

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

第 3 行有 $n$ 个用空格隔开的整数$a_1,a_2,\dots ,a_n$，$0\le a_i<m$，表示第 $i$ 副耳机原本的玄学值。

第 4 行一个整数 $q$，表示巨酱的操作总数。

接下来有 $q$ 行，每行 $4$ 个或 $5$ 个整数，第一个整数 cmd 是 $1$ 或 $2$，表示这个操作的种类。若 cmd 为 $1$，接下来还有 $4$ 个整数 $i,j,a,b$，表示巨酱增加一条计划，把耳机 $i\dots j$ 的玄学值应用变换 $x\mapsto (ax+b)modm$ （保证 $0\le a,b<m$）。若 cmd 为 $2$，接下来还有 $3$ 个整数 $i,j,k$，表示巨酱询问如果自己只作用变换 $i\dots j$，编号为 $k$ 的耳机玄学值最终会变成多少。保证两种操作的 $i,j$ 在解密后（如果数据是加密的）有 $i\le j$。

输出格式

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

样例一

input

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

output

3
4

样例二

input

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

output

3
4

样例三

见样例数据下载。

限制与约定

其中 x 为 0 和 1 中的任意数，特征值最左边为最高位。我们保证，同类型的测试点中加密与不加密的数据点各占 50%，且修改操作数不超过 $100000$，所有数的都可以用 int 存下。

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

时间限制：$8\mathtt{\text{s}}$

空间限制：$768\mathtt{\text{MB}}$

来源

中国国家队清华集训2014~2015 Day 4 - By 黄嘉泰 & 钟皓曦

下载

样例数据下载