One day, Subset Sum Problem! However, proved that it was NP-complete, so makes up a new problem about subset sums:

gave a question to solve: theEach of the subsets of the set has an -bit identifier , where the bit of is if the set contains , and if the set doesn't contain . Each set also has a value . There are queries that come in two different types:

`1 s v`

The set whose -bit identifier is has its value changed to .`2 a b`

Let and be the sets with identifiers and . Output the sum of the values of all sets such that . (Output if there are no such sets ).

Help

solve this modified subset sum problem!#### Input Specification

The first line contains and .

The next line contains , the values of the subsets of .

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

#### Output Specification

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

#### Constraints

##### Subtask 1 [20%]

##### Subtask 2 [30%]

for all type 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, and correspond to sets and . There are 4 possible sets that satisfy , which are , and the sum of their values is .

In the second query, and , so and . No sets satisfy , so the answer is .

The third query changed the value of to , and in the fourth query, the possible sets with are and . The sum of their values is .

## Comments