 Competitions

# IOI 2019 Azerbaijan Team Selection Contest (Day1 + Day2)

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 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`, 1q`105`) - the size of array and the number of queries. Next line contains the array elements `ai` (0`ai``109`).

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, 0v`109`).

#### 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
```