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: the
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 s vThe set whose -bit identifier is has its value changed to .
2 a bLet 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 ).
Helpsolve this modified subset sum problem!
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 the answer to each type query on a separate line.
Subtask 1 [20%]
Subtask 2 [30%]
for all type queries
Subtask 3 [50%]
No additional constraints.
3 4 1 1 2 3 5 8 13 21 2 4 7 2 1 2 1 3 7 2 1 3
47 0 8
Explanation for Sample Output
In the first query, and correspond to sets and B = . 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 .