You are given N numbers of the array (N ≤ 100000), all less than 10⁸ and greater than 0.

Now, you are given 2 types of queries:

• "1 x i" : Change the i-th number to x. (0 ≤ x ≤ 10⁸)
• "2 Op i1 i2": Compute the sum of all two elements taken at a time within index i1 to i2 (both inclusive) under the operation Op. Op could be XOR, OR or AND.

For example, let N=4, Query=3 and "10 20 30 40" be the Initial array.

Query:

2 OR 1 3
1 0 1
2 OR 1 3

Answer:

2 OR 1 3 → (10 OR 20) + (20 OR 30) + (10 OR 30)
1 0 1   → Now array becomes 0 20 30 40
2 OR 1 3 → (0 OR 20) + (20 OR 30) + (0 OR 30)

Example

Input:
4 3
10 20 30 40
2 OR 1 3
1 0 1
2 OR 1 3

Output
90
80

NOTE: If i1 is equal to i2, always output 0.

Click here to see my set of problems at Spoj.