## DMOPC '18 Contest 5 P6 - An XOR Problem

View as PDF

Points: 25 (partial)
Time limit: 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

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.

#### Constraints

is divisible by for every update

#### Input Specification

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 Specification

Output the weight of the minimum spanning tree after each of the updates.

#### Sample Input

3 2
1 2 3
2
1
1

#### Sample Output

3
3

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