Description

You need to help Chtholly maintain a 01 sequence $a$ of length $n$. There are $m$ operations:

• 1 l r: Set all numbers in interval $[l,r]$ to $0$.
• 2 l r: Set all numbers in interval $[l,r]$ to $1$.
• 3 l r: For all $a_i$ in $[l,r-1]$, change it to the bitwise OR of $a_i$ and $a_{i+1}$. These changes are performed simultaneously.
• 4 l r: For all $a_i$ in $[l+1,r]$, change it to the bitwise OR of $a_i$ and $a_{i-1}$. These changes are performed simultaneously.
• 5 l r: For all $a_i$ in $[l,r-1]$, change it to the bitwise AND of $a_i$ and $a_{i+1}$. These changes are performed simultaneously.
• 6 l r: For all $a_i$ in $[l+1,r]$, change it to the bitwise AND of $a_i$ and $a_{i-1}$. These changes are performed simultaneously.
• 7 l r: Query the sum over interval $[l,r]$.

This problem is forced online. Each $l,r$ needs to be XORed with the previous answer using $\operatorname{xor}$. If there has been no query before, then the previous answer is $0$.

Input Format

The first line contains two integers $n$ and $m$.

The second line contains $n$ integers representing the sequence $a$.

Then follow $m$ lines, each containing three integers $opt,l,r$, indicating which operation it is and the interval it applies to.

Output Format

For each query operation, output one line with one number as the answer.

5 5
0 1 0 0 1
3 2 5
5 2 5
2 2 2
6 1 5
7 1 5

1

Hint

Idea: nzhtl1477, Solution: nzhtl1477, Code: nzhtl1477, Data: nzhtl1477.

The sequence after each step:

For $30\%$ of the testdata, $n,m\leq 1000$.

For $50\%$ of the testdata, $n,m\leq 10^5$.

For another $30\%$ of the testdata, both the operations and the sequence are generated randomly.

For another $10\%$ of the testdata, $n,m\leq 10^6$.

Constraints: for $100\%$ of the testdata, $1\leq n,m\leq 3 \times 10^6$, $0\leq a_i\leq 1$.

Translated by ChatGPT 5