e-olymp
Competitions

IOI 2019 Azerbaijan Team Selection Contest (Day1 + Day2)

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) 1 l r - in this query on a segment [l, r] (1l < rn) you need to find the sum of all pairwise XOR, that is, the value

xorimg.png

2) 2 l r v - in this query on a segment [l, r] (1lrn) 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 (2n2 * 105, 1q105) - the size of array and the number of queries. Next line contains the array elements ai (0ai109).

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 (1l < rn). If the query of type 2, then given three numbers l, r and v (1lrn, 0v109).

Output

Print the answers to the query of type 1.

Time limit 2 second
Memory limit 128 MiB
Input example #1
3 3
1 2 3
1 1 3
2 1 3 2
1 1 2
Output example #1
6
3
Input example #2
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
Output example #2
30
15
26
49
Author Rashad Mammadov
Source 2019 İOİ Selection Round of Azerbaijan team