G. Bitwise And Equals
time limit per test
3 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

There is an array of integers $$$a_1, a_2, \ldots, a_n$$$, and there is an integer $$$X$$$.

You may perform the following operation zero or more times:

  • Select $$$i$$$, and increase $$$a_i$$$ by one.

Let $$$a'$$$ be the final state of the array. Your goal is to perform the operation above the smallest number of times such that $$$a'_1 \,\&\, a'_2 \,\&\, \ldots \,\&\, a'_n = X$$$. $$$\&$$$ denotes the bitwise AND operation.

There are $$$q$$$ such query integers $$$X$$$: $$$X_1, X_2, \ldots, X_q$$$. Compute the answer for each $$$X = X_i$$$. Note that all queries are processed separately and independently, from the same initial state $$$a$$$.

Input

The first line contains integers $$$n$$$ and $$$q$$$ ($$$2 \le n \le 200\,000$$$, $$$1 \le q \le 200\,000$$$) — the length of the array and the number of queries.

The second line contains integers $$$a_1, a_2, \ldots, a_n$$$ (for each $$$i$$$, $$$0 \le a_i \lt 2^{20}$$$).

The next $$$q$$$ lines each contain a single integer $$$X_i$$$ ($$$0 \le X_i \lt 2^{20}$$$).

Output

For each query $$$i$$$ out of $$$q$$$, print the smallest number of operations to get to the array $$$a'$$$ such that $$$a'_1 \,\&\, a'_2 \,\&\, \ldots \,\&\, a'_n = X_i$$$.

It's possible to show, that it's always possible to obtain such array $$$a'$$$ in finite number of operations.

Example
Input
5 4
6 4 7 5 4
0
2
4
6
Output
1
8
0
5
Note

For the first query, you can increase $$$i = 3$$$ ($$$a_i = 7$$$) and get the array $$$a = [6, 4, 8, 5, 4]$$$, then $$$6 \,\&\, 4 \,\&\, 8 \,\&\, 5 \,\&\, 4 = 0$$$.

For the third query, original array already matches condition: $$$6 \,\&\, 4 \,\&\, 7 \,\&\, 5 \,\&\, 4 = 4$$$.