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.

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 000
1 ≤ 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