E. Baby Ehab's X(OR)
time limit per test
1 second
memory limit per test
256 megabytes
input
orxor.in
output
standard output

Baby Ehab has finished studying bitwise operations. He especially loved the two operations bitwise $$$OR$$$ and bitwise $$$XOR$$$ (of course).

He thought he'd mess with Baby Badawy and play with.. Well.. His cubes. Baby Badawy had an array $$$a$$$ of cubes, lined up from left to right. The $$$i_{th}$$$ cube had a number $$$a_i$$$ written on it. On each of the following $$$q$$$ operations, he would do one of the following 2 updates:

  • $$$1$$$ $$$l$$$ $$$r$$$: for every cube between positions $$$l$$$ and $$$r$$$, Baby Ehab will replace the number on the $$$i_{th}$$$ cube with $$$a_i \space | \space (a_i - 1)$$$, where $$$|$$$ is the bitwise $$$OR$$$ operator.
  • $$$2$$$ $$$l$$$ $$$r$$$: for every cube between positions $$$l$$$ and $$$r$$$, Baby Ehab will replace the number on the $$$i_{th}$$$ cube with $$$a_i \space \oplus \space (a_i - 1)$$$, where $$$\oplus$$$ is the bitwise $$$XOR$$$ operator.

Baby Badawy decided to make a stand against Ehab's bullying and all the babysitters were behind our golden boy. He told Ehab that he can tell him the sum of all the numbers in the array after each operation.

You, a stranger, decided to help our golden boy. Can you?

Input

The first line contains 2 integers $$$n$$$ and $$$q$$$ $$$(1 \leq n, q \leq 3 \times 10 ^ 5 )$$$, the number of elements in the array $$$a$$$ and the number of operations.

The second line contains $$$n$$$ space-separated integers denoting the array $$$a$$$ $$$(1 \leq a_i \leq 3 \times 10 ^ 5 )$$$.

The following $$$q$$$ lines will each contain an update as described in the statement $$$(1 \leq l_i \leq r_i \leq n)$$$.

Output

After each update, print the sum of the array on a single line.

Examples
Input
3 3
1 2 3
1 1 3
2 2 2
2 1 3
Output
7
5
3
Input
5 5
5 5 5 5 5
1 5 5
2 1 1
2 2 3
1 3 4
2 1 5
Output
25
21
13
13
5