XOR-ing Murad
XOR-ing Murad
Murad likes XOR operation very much. All the day he calculates the XOR of different numbers.
Now Murad has the next problem. He is given array a of size n. Murad must answer q queries. The queries can be of two types:
1 l r - in this query on a segment [l, r] (1 ≤ l < r ≤ n) you need to find the sum of all pairwise XOR, that is, the value
2 l r v - in this query on a segment [l, r] (1 ≤ l ≤ r ≤ n) you need to XOR all elements with v.
Warning: here XOR is a bit operation xor.
Input data
First line contains two numbers n and q (2 ≤ n ≤ 2 * 10^5
, 1 ≤ q ≤ 10^5
) - the size of array and the number of queries. Next line contains the array elements a[i]
(0 ≤ a[i]
≤ 10^9
).
Next q lines contains the queries. First comes the query type, the number 1 or 2. If the query of type 1, then given two numbers l and r (1 ≤ l < r ≤ n). If the query of type 2, then given three numbers l, r and v (1 ≤ l ≤ r ≤ n, 0 ≤ v ≤ 10^9
).
Output data
Print the answers to the query of type 1.
Examples
3 3 1 2 3 1 1 3 2 1 3 2 1 1 2
6 3
4 6 4 8 7 8 1 2 4 2 1 2 2 1 3 4 2 1 1 8 1 1 3 1 1 4
30 15 26 49