Description

There are $2^n$ stars in the sky, numbered $0,1,\ldots,2^n-1$ in order. Each star has a brightness value. Initially, the brightness of star $i$ is $a_i$.

For two positive integers $a,b$, we define a Boolean operation $a\otimes b$. If, in the binary representation of $a$, every bit where $a$ is $1$ also has the corresponding bit of $b$ equal to $1$, then $a\otimes b$ is True; otherwise, it is False.
If the two numbers have different bit lengths in binary, align them to the right and pad zeros on the left. For example, for $1$ and $11$ (in binary), $1$ becomes $01$.

There are two types of operations on the brightness values:

1. $1$ $a$ $b$ $k$. For all $c$ such that $a\otimes c$ is True and $c\otimes b$ is True, add $k$ to the brightness of star $c$.

2. $2$ $a$ $b$. For all $c$ such that $a\otimes c$ is True and $c\otimes b$ is `True$, compute the sum of the brightness values of all such stars$c$, and output the result modulo $2^{32}$.

Input Format

The first line contains two integers $n,q$.

The second line contains $2^n$ integers separated by spaces, representing $a_0,a_1,\cdots,a_{2^n-1}$.

The next $q$ lines each describe one operation, in the format given in the Description.

Output Format

For each operation of type $2$, output one line containing the answer.

3 3
1 2 3 4 5 6 7 8
2 0 7
1 1 5 1
2 1 7

36
22

Hint

Sample Explanation

The first operation is a query. The binary representation of $0$ is $000$, and the binary representation of $7$ is $111$. At this time, all numbers satisfy the condition, so we take the sum of all numbers, which is $36$.

The second operation is an update. The binary representation of $1$ is $001$, and the binary representation of $5$ is $101$. We find that $c=1,5$ satisfy the condition, with binary representations $001$ and $101$ respectively, so $a_1,a_5$ change from $2,6$ to $3,7$.

The third operation is a query. The binary representation of $1$ is $001$, and the binary representation of $7$ is $111$. We find that $c=1,3,5,7$ satisfy the condition, with binary representations $001$, $011$, $101$, $111$ respectively. We need the sum $a_1+a_3+a_5+a_7=3+4+7+8=22$.

Constraints

This problem uses bundled testdata and has $4$ subtasks.

$Subtask 1(1\%)$: The answers match the sample.

$Subtask 2(9\%)$: $n \le 12,m \le 2\times 10^3$.

$Subtask 3(15\%)$: All type $2$ operations occur after type $1$ operations.

$Subtask 4(75\%)$: No additional restrictions.

For $100\%$ of the testdata, $1 \le n \le 16,1 \le m \le 2\times 10^5, 0 \le a,b \le 2^n-1,0 \le a_i,k \le 2^{32}-1$.

Friendly Reminder

To take modulo $2^{32}$, you can directly use an unsigned 32-bit integer type for computations. In c++, this is unsigned int.

That is, just let it overflow naturally and nothing will happen.

Translated by ChatGPT 5