Background

Time flows, leaving no trace.
In the night sky above the small town, countless sparkling stars shine like gemstones.
It is still the same sky, still the same town.
......
“Long time no see.”
“Before we knew it, so much time has passed...”
“But this town is still the town we once knew.”
“Only, we are no longer who we used to be.”
“Do you remember? We watched snow here together, and played games together...”
“But the game ending was already decided from the very beginning... that’s so mean...”
“Hehe, come to think of it, you’ve never beaten me......”
“I still remember what you said back then: whenever there is a piece of longing in this world, it will turn into a snowflake and fall here...”
“Yeah. As long as I look at the snow in winter, I can think of you. I know this must be your longing...”
“I can see it too, memories falling like snowflakes......”

The tiny bits of light in the sky blend together, clear and peaceful. The scene in front of you feels both familiar and unfamiliar.

“How about we stay a little longer, just like before......”
“With you, with the town, with the starry sky......”

Problem 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