P7346 [DSOI 2021] Reset to Zero.

 A chance to talk with the Witch of Greed is something rare for other people. For Q&A, only the two of us are needed. Let us skip the extra small talk; words alone are enough.  Your thirst for knowledge, curiosity, and greed—I acknowledge them all. Speak, what do you want to ask? Is it about the beast created against fate to save all living beings from hunger, the $\left \lceil \right. $ Witch of Gluttony $\left. \right \rfloor$ Daphne? Is it about the one who wanted to fill the world with love and granted emotions to non-humans, the $\left \lceil \right. $ Witch of Lust $\left. \right \rfloor$ Camilla? Is it about the one who lamented that the world is full of conflict, yet healed everyone with violence, the $\left \lceil \right. $ Witch of Wrath $\left. \right \rfloor$ Minerva? Is it about the one who, just to seek peace, drove the dragon to the far side of the great waterfall, the $\left \lceil \right. $ Witch of Sloth $\left. \right \rfloor$ Sekhmet? Is it about the one who relied on being young and innocent, yet punished the world without mercy, the $\left \lceil \right. $ Witch of Pride $\left. \right \rfloor$ Typhon? Is it about the embodiment of the desire for knowledge, who sought all wisdom in the world and would not even give up the world after death, the $\left \lceil \right. $ Witch of Greed $\left. \right \rfloor$ Echidna? Or is it about the $\left \lceil \right. $ Witch of Envy $\left. \right \rfloor$, the taboo $\left \lceil \right. $ “her” $\left. \right \rfloor$, who devoured all witches as her food and became an enemy of the world? 

#### ( **If you feel the statement is unclear, please visit “Input Format” to see a simplified version.**) #### ( **Please read the guarantees to ensure you can solve the problem.**) What I want to ask is only... Suppose I have a sequence $a$ of length $n$, indexed from $1\rightarrow n$, where $a_i$ denotes the $i$-th number. I will perform $m$ operations of four types, numbered in the given order: $\left \lceil \right. $ If I have two values $x$ and $y$, I will use shadow magic to XOR $y$ onto all $a_i$ such that $i \equiv 0 \pmod{x}$. $\left. \right \rfloor$ $\left \lceil \right. $ At the same time, I will reflect on myself and ask for the value of $a_x$ in the sequence. $\left. \right \rfloor$ $\left \lceil \right. $ After many loops, I have learned that only by perfectly seizing every opportunity can I gain a greater advantage. Therefore I will compare $a_x$ with my expectation $y$. If $a_x \le y$, I will loop back and execute the **shadow magic operations** among operations numbered $u \rightarrow v$. $\left. \right \rfloor$ $\left \lceil \right. $ Also, to prevent forgetting, I will loop back and execute operation number $x$. $\left. \right \rfloor$ As you know, save points in looping cannot be interleaved, so my loops will not intersect. Can you help me answer the questions in my mind?

The first line contains two integers $n$ and $m$, representing the length of the sequence and the number of operations.\ The second line contains $n$ integers $a_i$, representing the initial sequence.\ Then follow $m$ lines, each containing some integers. Line $i + 2$ describes operation number $i$. The first integer $op$ is one of $1 \rightarrow 4$: - $op = 1$ : Read 3 integers $1$, $x$, $y$. For all $i \equiv 0 \pmod{x}$ (that is, $x$, $2x$ … $kx$, where $k \in Z^+$ and $k \times x \le n$), set $a_i = a_i \oplus y$ ($\oplus$ denotes XOR). - $op = 2$ : Read 2 integers $2$, $x$, and output $a_x$. - $op = 3$ : Read 5 integers $3$, $x$, $y$, $u$, $v$. If $a_x \le y$, execute all operations with $op = 1$ among operations numbered $u \rightarrow v$; otherwise ignore this operation. It is guaranteed that $u \le v < i$. - $op = 4$ : Read 2 integers $4$, $x$, and execute operation number $x$. It is guaranteed that $x < i$. Because loops do not interleave, the problem guarantees: - If $op_i = 3$, **then among operations numbered $u\rightarrow i-1$, the type is definitely not $3$ or $4$.** - Also, if $op_i = 4$, **then among operations numbered $x+1\rightarrow i-1$, the type is definitely not $3$ or $4$ (but operation $x$ itself may be of type $3$ or $4$, i.e., it can be called).** In mathematical language: **if $op_i = 3$, then there are no $3$ or $4$ operations in $[u, i)$; if $op_i = 4$, then there are no $3$ or $4$ operations in $(x, i)$.**

Output several lines.\ Each line is the answer to a query of type $op = 2$, or the answer produced by a query operation that is invoked by a type $op = 4$ call.

**[For sample 2, the values of the sequence during each operation are given below.]** | Operation | $a_1$ | $a_2$ | $a_3$ | $a_4$ | $a_5$ | $a_6$ | Explanation | | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: |:----------:| | None | 2 | 3 | 7 | 1 | 9 | 0 | Input | | $1_{st}$ | 0 | 1 | 5 | 3 | 11 | 2 | $1\rightarrow6$ all $xor$ $2$ | | $2_{nd}$ | 2 | 3 | 7 | 1 | 9 | 0 | $a_4 = 3 \le 10$, perform operation $1$ | | $3_{rd} $ | 2 | 3 | 4 | 1 | 9 | 3 | $3$ $/$ $6$ both $xor$ 3 | | $4_{th} $ | 2 | 3 | 7 | 1 | 9 | 0 | $3$ $/$ $6$ both $xor$ 3 | | $5_{th} $ | 2 | 3 | 7 | 1 | 9 | 0 | Output $a_5$ | | $6_{th} $ | 2 | 3 | 7 | 1 | 9 | 0 | Output $a_5$ | | $7_{th} $ | 2 | 11 | 7 | 9 | 9 | 8 | $2$ $/$ $4$ $/$ $6$ all $xor$ $8$ | | $8_{th} $ | 2 | 11 | 7 | 9 | 9 | 8 | Output $a_5$ | | $9_{th} $ | 2 | 11 | 7 | 9 | 9 | 8 | Output $a_5$ | | $10_{th} $ | 2 | 11 | 7 | 9 | 9 | 8 | Output $a_6$ | ------------ **[Explanation of the “guarantees”]** For example, suppose the operation types are $op_1 = 1$, $op_2 = 4$, $op_3 = 2$, $op_4 = 3$, $op_5 = 1$, $op_6=4$. Then for $op_4$, the corresponding $u$ and $v$ can only be $u = 3$, $v = 3$, because $u \le 2$ would make its range contain an operation of type $4$. For $op_6$, the corresponding $x$ can be $4$ or $5$, because then there are no type $3$ or $4$ operations between the right side of $x$ and the left side of operation $6$. ------------ **[Constraints]**\ **This problem uses bundled testdata.** You must pass all test points in a subtask to obtain the score of that subtask. | Subtask | Special Property | Score | | :----------: | :----------: |:--------:| | 1 | Is sample $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$, no operation $4$ | 10 pts | | 6 | $n \le 10^5$, $m \le 5 \times 10^5$, no operation $3$ | 10 pts | | 7 | $n \le 10^5$, $m \le 5 \times 10^5$, random testdata | 18 pts | | 8 | $n \le 10^5$, $m \le 5 \times 10^5$ | 32 pts | For $100\%$ of the data, it is guaranteed that $1 \le n \le 10^5$, $m \le 5 \times 10^5$, and all values during the process and in the results are within the range of `int`. Translated by ChatGPT 5