Background

To filter out incorrect algorithms, we changed the time limit to 680 ms.

Problem Description

LAR has $2^n$ apples. The apples are numbered from $0$ to $2^n - 1$. The value of the apple with number $i$ is $v_i$.

If $A \operatorname{or} B = A$, then we say that $A$ contains $B$ (where $\operatorname{or}$ is bitwise OR).

Since LAR has too many apples, he does not know how to choose apples. He wants to perform some operations so that it is more convenient for him to eat apples.

There are two types of operations, for a total of $q$ operations:

• $1\ S$: Query the sum of values of all apples whose indices are contained in $S$.
• $2\ S\ A$: Change the value of the apple with index $S$ to $A$ (set $v_S$ to $A$).

Input Format

The first line contains two integers $n$ and $q$, where $q$ is the number of operations.

The second line contains $2^n$ numbers. The $i$-th number represents the value of $v_{i-1}$.

The next $q$ lines each describe one operation that LAR will perform, as detailed above.

Output Format

For each operation of type $1$, output one number, which is the answer to the query.

2 5
1 2 3 2
1 2
2 0 4
1 2
2 3 1
1 3

4
7
10

Hint

Sample Explanation

Initially, $v = [1,2,3,2]$.

In the first operation, we query the sum of values of all apples whose indices are contained in $2$. The numbers contained in $2$ are $0,2$, so the answer is $v_0 + v_2 = 4$.

In the second operation, we change $v_0$ to $4$, so now $v = [4,2,3,2]$.

In the third operation, we query the sum of values of all apples whose indices are contained in $2$. The numbers contained in $2$ are $0,2$, so the answer is $v_0 + v_2 = 7$.

In the fourth operation, we change $v_3$ to $1$, so now $v = [4,2,3,1]$.

In the fifth operation, we query the sum of values of all apples whose indices are contained in $3$. The numbers contained in $3$ are $0,1,2,3$, so the answer is $v_0 + v_1 + v_2 + v_3 = 10$.

Constraints

This problem uses bundled testdata.

For $100\%$ of the testdata, it is guaranteed that $1 \le n \le 20$, $1 \le q \le 3 \times 10^5$, and $0 \le v_i \le 2^{31} - 1$.

Hint: The input size of this problem is large, so please use fast input. Please pay attention to the constant factors in your code.

Translated by ChatGPT 5