XOR-ing Murad#9030
Murad likes operation very much. All the day he calculates the of different numbers.
Now Murad has the next problem. He is given array of size . Murad must answer queries. The queries can be of two types:
1) - in this query on a segment [, ] (1 \leq l < r \leq n) you need to find the sum of all pairwise , that is, the value
2) - in this query on a segment [, ] (1 \leq l \leq r \leq n) you need to all elements with .
**Warning**: here is a bit operation .
First line contains two numbers and (2 \leq n \leq 2 \cdot 10^5, 1 \leq q \leq 10^5) - the size of array and the number of queries. The next line contains elements of the array a_i (0 \leq a_i \leq 10^9).
The next lines contain the queries. First comes the query type: either or . If the query is of type , then two numbers are given and (1 \leq l < r \leq n). If the query is of type , then three numbers are given , and (1 \leq l \leq r \leq n, 0 \leq v \leq 10^9).
Print the answers to all queries of type .
Example 1
Example 2