A graph has $N$ nodes labelled from $1$ to $N$ where node $i$ is assigned a $K$-bit integer $x_i$. Every pair of nodes $(i,j)$ has an edge between them with weight $x_i\oplus x_j$ where $\oplus$ 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 $Q$ updates of the form c. For each update, $x_i$ is changed to $(x_i+c)mod{2}^K$ for every $i=1,2,\dots ,N$. After each update, output the weight of the minimum spanning tree.

Constraints

For all subtasks:

$0\le x_i,c\le 2^K-1$

$1\le N,Q\le 20000$

Subtask 1 [20%]

$1\le K\le 7$

Subtask 2 [20%]

$1\le K\le 14$

$1\le Q\le 20$

Subtask 3 [20%]

$6\le K\le 14$

$c$ is divisible by $2^5$ for every update.

Subtask 4 [40%]

$1\le K\le 14$

Input Specification

The first line will contain two space-separated integers, $N$ and $K$.
The second line will contain $N$ space-separated integers, $x_1,x_2,\dots ,x_N$.
The third line will contain a single integer, $Q$.
The next $Q$ lines will each contain a single integer, $c$.

Output Specification

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

Sample Input

3 2
1 2 3
2
1
1

Sample Output

3
3

Explanation for Sample

After the first update, the $x$ values are $0,2,3$. Then the minimum total weight is $(0\oplus 2)+(2\oplus 3)=3$. After the second update, the $x$ values are $0,1,3$. The minimum total weight is $(0\oplus 1)+(1\oplus 3)=3$.