Description

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

（ 请查看题目保证以确保能 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$

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

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

Input Format

第一行两个数 $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$ 操作。

Output Format

输出若干行。
每一行为 $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

Hint

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

【关于“保证”的说明】

例如一串操作类型为 $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 范围内。