Description

( 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?

Input Format

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 Format

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.

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

[For sample 2, the values of the sequence during each operation are given below.]

[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