A graph has nodes labelled from to where node is assigned a -bit integer . Every pair of nodes has an edge between them with weight where denotes the XOR operation. You want to know the total weight of this graph's minimum spanning tree. However, the values assigned to each node sometimes change. In particular, you will receive updates of the form
c. For each update, is changed to modulo for every . After each update, output the weight of the minimum spanning tree.
For all subtasks,
Subtask 1 [20%]
Subtask 2 [20%]
Subtask 3 [20%]
is divisible by for every update
Subtask 4 [40%]
The first line will contain two space-separated integers, and .
The second line will contain space-separated integers, .
The third line will contain a single integer, .
The next lines will each contain a single integer, .
Output the weight of the minimum spanning tree after each of the updates.
3 2 1 2 3 2 1 1
Explanation for Sample
After the first update, the values are . Then the minimum total weight is . After the second update, the values are . The minimum total weight is .