题目背景

能和强欲魔女谈话的机会，对其他人来说是不可多得的 。

进行问答只需要彼此而已，多余的闲功夫就省了吧 ，只有言语就够了 。

你的求知欲、好奇心、强欲，我都给予肯定 。

说吧，你想问什么 ？

是关于为振救苍生免于饥饿，违背天命而创造出的野兽 $\left \lceil \right.$ 暴食魔女 $\left. \right \rfloor$ 达芙妮的事吗 ？

是那个打算用爱填满世界，而赐予非人之物情感 $\left \lceil \right.$ 色欲魔女 $\left. \right \rfloor$ 卡蜜拉的事吗？

是一边哀叹着世界充满争斗，却用暴力治愈所有人 $\left \lceil \right.$ 愤怒魔女 $\left. \right \rfloor$ 密涅瓦的事吗？

是仅仅为了追求安稳，就把龙赶到大瀑布彼端 $\left \lceil \right.$ 怠惰魔女 $\left. \right \rfloor$ 塞赫麦特的事吗？

是仗着年幼天真，却毫无慈悲地制裁世人 $\left \lceil \right.$ 傲慢魔女 $\left. \right \rfloor$ 缇丰的事吗？

是为了渴求世上一切智慧，就连死后的世界都舍不得放弃 那位知识欲望的化身 $\left \lceil \right.$ 强欲魔女 $\left. \right \rfloor$ 艾姬多娜的事吗？

还是说，是消灭所有魔女做自己的食粮，并与世界为敌的 $\left \lceil \right.$ 嫉妒魔女 $\left. \right \rfloor$ 那位令人忌讳的 $\left \lceil \right.$ 她 $\left. \right \rfloor$？

题目描述

（ 若觉得题意不清，请造访 “输入格式” 查看简明化题意。）

（ 请查看题目保证以确保能 solve the problem .）

我想问的只有 ....

如果我有一串长度为 $n$ 的序列 $a$ ，编号从 $1\rightarrow n$ , $a_i$ 表示第 $i$ 个数.

我共将进行 $m$ 次四种类型的操作，其编号为给出的顺序 ：

$\left \lceil \right.$ 如果我有 $x$ 、$y$ 两值，我会用阴魔法将序列中所有下标 $i \equiv 0 \pmod{x}$ 的 $a_i$ 异或上 $y$ 。$\left. \right \rfloor$

$\left \lceil \right.$ 同时我也会三省自身，问问自己序列中 $a_x$ 的值 。$\left. \right \rfloor$

$\left \lceil \right.$ 多次轮回让我明白，只有完美把握住每一次机遇，我才可以占据更大的有利因素。因而我将估量 $a_x$ 和我的预期 $y$ ，如果 $a_x \le y$ ，我将轮回并执行编号为 $u \rightarrow v$ 的操作中的 阴魔法操作 。$\left. \right \rfloor$

$\left \lceil \right.$ 另外，为了防止遗忘，我还会轮回执行编号为 $x$ 的操作。$\left. \right \rfloor$

你也知道，轮回的存档点是不能交错的，所以我的轮回是不会相交的。

请问你，能否帮我，回答我心中的问答？

输入格式

第一行两个数 $n$ ，$m$ ，表示序列长度和操作数。
第二行 $n$ 个数 $a_i$ ，表示初始序列。
接下来有 $m$ 行，有若干数字，第 $i + 2$ 行表示编号为 $i$ 的操作，第一个数 $op$ 为 $1 \rightarrow$ 4 的一个 :

• $op = 1$ : 读入 3 个数 $1$ , $x$ , $y$ , 对 $\forall$ $i \equiv 0 \pmod{x}$（ 也就是 $x$ , $2x$ … $kx$，$k \in Z^+$ 且 $k \times x \le n$ ）, $a_i = a_i \oplus y$（$\oplus$ 表示异或）。
• $op = 2$ : 读入 2 个数 $2$ , $x$ ，输出 $a_x$ 。
• $op = 3$ : 读入 5 个数 $3$ , $x$ , $y$ , $u$ , $v$ , 若 $a_x \le y$，执行编号为 $u \rightarrow v$ 内所有 $op = 1$ 的操作，否则无视此操作。保证 $u \le v < i$ 。
• $op = 4$ : 读入 2 个数 $4$ , $x$ ， 执行编号为 $x$ 的操作。保证 $x < i$ 。

因为轮回不交错：题目保证，若 $op_i = 3$，则编号为 $u\rightarrow i-1$ 的操作，类型一定不为 $3$ or $4$ ； 同时，若 $op_i = 4$ ，则编号为 $x+1\rightarrow i-1$ 的操作，类型一定不为 $3$ or $4$ （ 但是 $x$ 位置可为 $3$ 、 $4$ 类型操作，即可以调用 ）。

用数学语言就是：若 $op_i = 3$ ，则 $[u , i)$ 一定没有 $3$ or $4$ 操作 ; 若 $op_i = 4$ , 则 $(x, i)$ 一定没有 $3$ or $4$ 操作。

输出格式

输出若干行。
每一行为 $op=2$ 类型操作的询问结果或 $op = 4$ 类型操作调用的询问操作的询问结果。

6 10
1 1 4 5 1 4
1 1 6
1 2 8
4 2
4 3
4 4
4 5 
4 6
2 1
2 3
2 4

7
2
3

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

9
0
9
9
8

提示

【对于样例 2，下面给出其每个操作过程中序列的值】

操作	$a_1$	$a_2$	$a_3$	$a_4$	$a_5$	$a_6$	说明
无	2	3	7	1	9	0	读入
$1_{st}$	0	1	5	3	11	2	$1\rightarrow6$ 都 $xor$ $2$
$2_{nd}$	2	3	7	1	9	0	$a_4 = 3 \le 10$ ，进行 $1$ 操作
$3_{rd}$			4			3	$3$ $/$ $6$ 都 $xor$ 3
$4_{th}$			7			0
$5_{th}$							输出 $a_5$
$6_{th}$
$7_{th}$		11		9		8	$2$ $/$ $4$ $/$ $6$ 都 $xor$ $8$
$8_{th}$							输出 $a_5$
$9_{th}$
$10_{th}$							输出 $a_6$

---

【关于“保证”的说明】

例如一串操作类型为 $op_1 = 1$、$op_2 = 4$、$op_3 = 2$、$op_4 = 3$、$op_5 = 1$、$op_6=4$。那么 $op_4$ 所对应的 $u$、 $v$ 只能为 $u = 3$ 、$v = 3$ ，因为 $u \le 2$ 会导致其范围内包含 $4$ 操作；而 $op_6$ 所对应的 $x$ 可以是 $4$ 或 $5$ ，因为这样子 $x$ 的右边到编号 $6$ 的左边都没有 $3$ 、$4$ 操作。

---

【数据范围】
本题采用捆绑测试。 你必须通过 Subtask 中所有的测试点才能获得该 Subtask 的分数。 | Subtask | 特殊性质 | 分值 | | :----------: | :----------: |:--------:| | 1 | 为样例 $2$ | 2 pts| | 2 | $n \le 10$ , $m \le 10$ | 8 pts | | 3 | $n \le 1000$ , $m \le 1000$ | 10 pts | | 4 | $n \le 10^4$ , $m \le 10^4$ | 10 pts | | 5 | $n \le 10^5$ , $m \le 5 \times 10^5$ , 无操作 $4$ | 10 pts | | 6 | $n \le 10^5$ , $m \le 5 \times 10^5$ , 无操作 $3$ | 10 pts | | 7 | $n \le 10^5$ , $m \le 5 \times 10^5$ , 数据随机 | 18 pts | | 8 | $n \le 10^5$ , $m \le 5 \times 10^5$| 32 pts | 对于 $100\%$ 的数据，保证 $1 \le n \le 10^5$ , $m \le 5 \times 10^5$，保证过程及结果的所有值都在 int 范围内。