P7346 【DSOI 2021】归零

 能和强欲魔女谈话的机会，对其他人来说是不可多得的 。 进行问答只需要彼此而已，多余的闲功夫就省了吧 ，只有言语就够了 。  你的求知欲、好奇心、强欲，我都给予肯定 。 说吧，你想问什么 ？ 是关于为振救苍生免于饥饿，违背天命而创造出的野兽 $\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$ 类型操作调用的询问操作的询问结果。

**【对于样例 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} $ | 2 | 3 | 4 | 1 | 9 | 3 |$3 $ $/$ $6$ 都 $xor$ 3| | $4_{th} $ | 2 | 3 | 7 | 1 | 9 | 0 |$3 $ $/$ $6$ 都 $xor$ 3| | $5_{th} $ | 2 | 3 | 7 | 1 | 9 | 0 | 输出 $a_5$| | $6_{th} $ | 2 | 3 | 7 | 1 | 9 | 0 | 输出 $a_5$ | | $7_{th} $ | 2 | 11 | 7 | 9 | 9 | 8 | $2$ $/$ $4$ $/$ $6$ 都 $xor$ $8$| | $8_{th} $ | 2 | 11 | 7 | 9 | 9 | 8 | 输出 $a_5$ | | $9_{th} $ | 2 | 11 | 7 | 9 | 9 | 8 | 输出 $a_5$| | $10_{th} $ | 2 | 11 | 7 | 9 | 9 | 8 | 输出 $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 范围内。