Simple statement. You have a 1-indexed array with $N$ integers, and you want to perform some $Q$ queries on it.

1. 1 p x: change index p to x, where $1\le x\le {10}^8$
2. 2 l r: perform the OR bitwise operation on all pairs from l to r, inclusive, then sum them
3. 3 l r: perform the AND bitwise operation on all pairs from l to r, inclusive, then sum them
4. 4 l r: perform the XOR bitwise operation on all pairs from l to r, inclusive, then sum them

Input Specification

The first line will contain $N$ and $Q$, $1\le N\le {10}^5$, $1\le Q\le {10}^4$.

The second line will contain $N$ integers.

The next $Q$ lines will contain valid queries.

For 30% of the points, $\{N,x\}\le 10$, $Q\le 50$.

Output Specification

For each query from 2 to 4, output the sum.

Sample Input 1

6 1
4 4 8 10 4 6
2 3 6

Sample Output 1

70

Explanatioin

For the query from $L=3$ to $R=6$, there are $6$ pairs:

$8|10=10$, $8|4=12$, $8|6=14$, $10|4=14$, $10|6=14$, $4|6=6$.

So the total sum is $10+12+14+14+14+6=70$.