XORin discovers an interesting function called Elf. XORina has given XORin an array A of N integers and Q queries. The queries are of 2 types:

1 ≤ A

**1 p x**- the element on the position p changes his value to x (A_{p}=x)**2 a b**- find the sum of Elf(i,j) for each a ≤ i ≤ j ≤ b, where Elf(i,j)=A_{i}xor A_{i+1}xor ... xor A_{j}

**print the responses to the 2nd type of queries.**## Input

The first line of the input contains n, the size of the array. The second line of the input contains m, the number of queries. The third line of the input contains n numbers, the initial elements of the array. On the next m lines each line contains a query. The first type of query is 1 p x (1 ≤ p ≤ n and 0 ≤ x ≤ 1000). The second type of query is 2 a b (1 ≤ a ≤ b ≤ n).## Output

The output contains the answer to the second type of queries, each answer on a line. Print the answer modulo**4001**## Constraints

1 ≤ N, M ≤ 100 0001 ≤ A

_{i}≤ 1 000## Sample

Input | Output |
---|---|

4 8 1 2 3 4 2 1 2 1 1 2 2 1 3 2 1 4 1 3 7 2 1 3 1 4 5 2 1 4 | 6 11 34 23 32 |