A. Queries
time limit per test
2.25 seconds
memory limit per test
128 megabytes
input
standard input
output
standard output

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 (Ap=x)

2 a b - find the sum of Elf(i,j) for each a ≤ i ≤ j ≤ b, where Elf(i,j)=Ai xor Ai + 1 xor ... xor Aj.

Your task is to 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 (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).

Output

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

Examples
Input
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
Output
6
11
34
23
32