One day, PlasmaVortex gave insect a question to solve: the Subset Sum Problem! However, insect proved that it was NP-complete, so PlasmaVortex makes up a new problem about subset sums:

Each of the $2^N$ $(1\le N\le 18)$ subsets of the set $\{1,2,\dots ,N\}$ has an $N$-bit identifier $s$, where the $i^{\text{th}}$ bit $(1\le i\le N)$ of $s$ is $1$ if the set contains $i$, and $0$ if the set doesn't contain $i$. Each set also has a value $V_s$ $(0\le s<2^N,1\le V_s\le {10}^6)$. There are $Q$ queries that come in two different types:

1. 1 s v The set whose $N$-bit identifier is $s$ has its value changed to $v$. $(0\le s<2^N,1\le v\le {10}^6)$
2. 2 a b Let $A$ and $B$ be the sets with identifiers $a$ and $b$ $(0\le a,b<2^N)$. Output the sum of the values of all sets $X$ such that $A\subseteq X\subseteq B$. (Output $0$ if there are no such sets $X$).

Help insect solve this modified subset sum problem!

Input Specification

The first line contains $N$ and $Q$. $(1\le N\le 18,1\le Q\le {10}^5)$

The next line contains $V_0,V_1,V_2,\dots ,V_{2^N-1}$, the values of the $2^N$ subsets of $\{1,2,\dots ,N\}$. $(1\le V_0,V_1,V_2,\dots ,V_{2^N-1}\le {10}^6)$

Each of the next $Q$ lines contains a query in the format specified above.

Output Specification

Output the answer to each type $2$ query on a separate line.

Constraints

Subtask 1 [20%]

$1\le N\le 10$

Subtask 2 [30%]

$a=0$ for all type $2$ queries.

Subtask 3 [50%]

No additional constraints.

Sample Input

3 4
1 1 2 3 5 8 13 21
2 4 7
2 1 2
1 3 7
2 1 3

Sample Output

47
0
8

Explanation for Sample Output

In the first query, $a=4={100}_2$ and $b=7={111}_2$ correspond to sets $A=\{1\}$ and $B=\{1,2,3\}$. There are 4 possible sets $X$ that satisfy $A\subseteq X\subseteq B$, which are $\{1\},\{1,2\},\{1,3\},\{1,2,3\}$, and the sum of their values is $5+13+8+21=47$.

In the second query, $a=1={001}_2$ and $b=2={010}_2$, so $A=\{3\}$ and $B=\{2\}$. No sets $X$ satisfy $A\subseteq X\subseteq B$, so the answer is $0$.

The third query changed the value of $\{2,3\}$ to $7$, and in the fourth query, the possible sets $X$ with $A=\{3\}\subseteq X\subseteq \{2,3\}$ are $X=\{3\}$ and $X=\{2,3\}$. The sum of their values is $1+7=8$.