Background

What is that?
【Not the Sixth Beast, but a new beast?】
【I have never seen that thing before.】

【All personnel retreat.】
【An unexpected beast has been confirmed.】
【Based on this situation, confirm the operation as a failure and abandon Island No. 15.】
How could this be...

I made a promise with him.
We must come back alive, no matter what.

I will tell him, “I’m back,” and then taste the butter cake.
So if the world ends, I will be in big trouble.

A forest melting into the morning mist.
Ah...?

【Milk traces, dazzling petals, a whirlwind air mass.】
【A herring hung on the wall, an upside-down hedgehog, an organ in a bag.】
What is this...?

Actually... you really want to fight, right?
Although I do not know what you are planning, it is enough already.

You do not need to fight anymore.
Because your fight has already been inherited by me, by us.
【Actually, I am very grateful to you.】
【All this time, all I could think about was dying.】

【Longing to go back to those guys waiting for me, that was my only wish.】
【But after meeting you, I changed a little.】
【I started longing for a place to belong again.】
【After meeting you, I found some salvation.】
【Being able to wait until you return safely, right now I...】
【Well, you could say I feel a bit of happiness.】
Ah...?

【N-no... wait, do not distance yourself from me so directly.】
【And do not make that face like “what is this shameless creature doing.”】
【But then again, you observed me very carefully.】
Haha...
Because I fell for you~


【I cannot help it.】
If you go, I will be angry, I will rage.
【Chtholly...】

【Sorry.】

I will wait for you.

I will wait for you, so you must come back.

【I promise, I will definitely come back.】
Mm.
It is a promise~

Problem 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