You need to help Chtholly maintain a 01 sequence $a$ of length $n$, with $m$ operations:

• 1 l r: Set all numbers in the range $[l, r]$ to $0$.
• 2 l r: Set all numbers in the range $[l, r]$ to $1$.
• 3 l r: For all $a_i$ in $[l, r-1]$, update $a_i$ to $a_i \lor a_{i+1}$. These updates occur simultaneously.
• 4 l r: For all $a_i$ in $[l+1, r]$, update $a_i$ to $a_i \lor a_{i-1}$. These updates occur simultaneously.
• 5 l r: For all $a_i$ in $[l, r-1]$, update $a_i$ to $a_i \land a_{i+1}$. These updates occur simultaneously.
• 6 l r: For all $a_i$ in $[l+1, r]$, update $a_i$ to $a_i \land a_{i-1}$. These updates occur simultaneously.
• 7 l r: Query the sum of the range $[l, r]$.

This problem is forced online. Each $l$ and $r$ must be XORed with the previous answer. If there has been no previous query, the previous answer is $0$.

Input

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

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

The following $m$ lines each contain three integers $opt, l, r$, representing the operation type and the corresponding range.

Output

For each query operation, output one integer per line representing the answer.

Examples

Input 1

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

Output 1

1

Note 1

The sequence state at each step: $$0\ 1\ 0\ 0\ 1$$ $$0\ 1\ 0\ 1\ 1$$ $$0\ 0\ 0\ 1\ 1$$ $$0\ 1\ 0\ 1\ 1$$ $$0\ 0\ 0\ 0\ 1$$ $$0\ 0\ 0\ 0\ 1$$

Subtasks

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

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

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

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

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

For $100\%$ of the data, $1 \leq n, m \leq 3 \times 10^6$, $0 \leq a_i \leq 1$.