## UTS Open '18 P6 - Subset Sum

View as PDF

Points: 25 (partial)
Time limit: 1.0s
Java 8 2.5s
Memory limit: 256M

Author:
Problem type

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 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. 1 s v The set whose -bit identifier is has its value changed to .
2. 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 insect solve this modified subset sum problem!

#### Input Specification

The first line contains and .

The next 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.

for all type queries.

#### 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 .