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
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
Print the answers to the query of type 1.