Apple Selection Operations

LAR has (2^n) apples numbered from (0) to (2^n - 1), where the apple with index (i) has a value (v_i).

We say that an integer (A) contains an integer (B) if (A \operatorname{or} B = A) (here (\operatorname{or}) denotes the bitwise OR operation). In other words, (B) is a subset (in the bit representation) of (A).

LAR finds it difficult to choose apples, so he performs a series of operations to make the selection process easier. There are (q) operations in total, and each operation is one of the following two types:

1. Query Operation: 1 S — output the sum of values (v_i) for all apples whose index (i) satisfies (S \operatorname{or} i = S) (i.e. (i) is a submask of (S)).
   
2. Update Operation: 2 S A — update the value of the apple with index (S) to (A) (i.e. set (v_S = A)).

inputFormat

The first line contains two integers (n) and (q), where (n) indicates that there are (2^n) apples, and (q) is the number of operations. The second line contains (2^n) integers (v_0, v_1, \ldots, v_{2^n-1}) representing the initial values of the apples. Each of the following (q) lines describes an operation in one of the following two formats:

• 1 S — a query operation, where you should output the sum of values of all apple indices \(i\) such that \(S \operatorname{or} i = S\) (i.e. \(i\) is a submask of \(S\)).
• 2 S A — an update operation, which sets \(v_S\) to \(A\).

outputFormat

For each query operation (type 1), output a single line containing the required sum.

sample

2 3
1 2 3 4
1 3
2 1 10
1 3

10
18