When they got to the camp, Manny and Sid found an array of numbers in it. Then they wanted to play a game with it. They will approach the array in some order and perform operations with it.

When Manny approaches an array, he can change the value of one element in it to any other. When Seed approaches the array, he selects two numbers a and b (1 ≤ a ≤ b ≤ n). After that, for all possible l and r such that a ≤ l ≤ r ≤ b, he will take an array subsegment from l to r (inclusive), calculate xor (bitwise exclusive OR) of its elements, and find the sum of all received numbers.

However, the friends have to keep going and don't have time to play. As everyone knows, mammoths have a perfect memory. So Manny memorized the array they found and all the moves they were going to make in the game and decided to play that game along the way. Help him determine what numbers Sid would get on his moves.

Input

The first line contains two integers n and m (1 ≤ n, m ≤ 105) - the length of array and the number of moves in the game. The next line contains n integers vi (0 ≤ vi ≤ 108) - the initial array.

Each of the next m lines contains three numbers - the description of the moves.

• 1 i x - Manny changed the value of element with number i to x (1 ≤ i ≤ n, 0 ≤ x ≤ 108).
• 2 a b - Sid chose a pair of numbers a and b (1 ≤ a ≤ b ≤ n).

Output

For each Sid's move, print the resulting amount on the new line.