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, 3, \dots, N\}~ has an ~N~-bit identifier ~s~, where the ~i^{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, 3, \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~.