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
Letand
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