# 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**] (**1** ≤ **l** < **r** ≤ **n**) 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**] (**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`

) - the size of array and the number of queries. Next line contains the array elements ^{5}`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**.

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