402367: GYM100739 A Queries

Memory Limit:128 MB Time Limit:0 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

A. Queriestime limit per test2.25 secondsmemory limit per test128 megabytesinputstandard inputoutputstandard 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.

ExamplesInput
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

加入题单

上一题 下一题 算法标签: