402367: GYM100739 A Queries

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 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.

Your task is to print the responses to the 2nd type of queries.

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 (1 ≤ n, m ≤ 100000). The third line of the input contains n numbers, the initial elements of the array (each of them is between 1 and 1000). 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).

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

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