## 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
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

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 .