Game with array#11266
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 Sid approaches the array, he selects two numbers and ( ≤ ≤ ≤ ). After that, for all possible and such that ≤ ≤ ≤ , he will take an array subsegment from to (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.
The first line contains two integers and ( ≤ , ≤ 10^5) - the length of array and the number of moves in the game. The next line contains integers v_i ( ≤ v_i ≤ 10^8) - the initial array.
Each of the next lines contains three numbers - the description of the moves.
- Manny changed the value of element with number to ( ≤ ≤ , ≤ ≤ 10^8).
- Sid chose a pair of numbers and ( ≤ ≤ ≤ ).
For each Sid's move, print the resulting sum on the new line.
Example 1