P10408 "SMOI-R1" Apple

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

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$).

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.

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

### 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.** | Subtask ID | $n \le$ | $q \le$ | Special Property | Score | | - | - | - | - | - | | $1$ | $10$ | $10^4$ | None | $10$ | | $2$ | $16$ | $3 \times 10^5$ | None | $20$ | | $3$ | $20$ | $3 \times 10^5$ | Only operation 1 | $10$ | | $4$ | $20$ | $10^5$ | None | $20$ | | $5$ | $20$ | $3 \times 10^5$ | None | $40$ | 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