Missing Trash

After a thorough yard cleanup, the residents of Evstigraf's building bagged up the leaves and litter they had gathered and left the bags out overnight. The next morning, all the trash was gone. The only thing left is a strange device labeled 'УсТнЫй СчЁт 3000'. The thief left it as a hint, so you need to figure out the device before you can learn anything about the thief.

The device tests your mental arithmetic. It shows an array $a_1, \ldots, a_n$, then asks for operations on segments $[l, r]$:

1. Compute $\sum_{i=l}^{r} (a_i \oplus i)$, where $\oplus$ is the XOR of two numbers.
2. Set every element of $[l, r]$ to $x$.
3. Apply a bitwise AND, OR, or XOR with $x$ to every element of $[l, r]$.

The first line contains two integers $n$ and $m$, the number of elements in the array and the number of queries ($1 \le n, m \le 10^5$).

The second line contains $n$ integers $a_1, \ldots, a_n$ ($0 \le a_i < 2^{15}$).

Each of the next $m$ lines describes a query.

• Type 1: 1 $l$ $r$
• Type 2: 2 $l$ $r$ $x$
• Type 3: 3 $l$ $r$ $x$ $c$, where $c$ is the operation: & for AND, | for OR, or ^ for XOR.

In every query, $1 \le l \le r \le n$ and $0 \le x < 2^{15}$.

For each query of type 1, print the requested sum on its own line.