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~.