CF2161G.Bitwise And Equals

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

给定一个整数数组 $a_1, a_2, \ldots, a_n$ 和一个整数 $X$。

你可以执行以下操作零次或多次：

• 选择下标 $i$，并将 $a_i$ 的值加一。

设 $a'$ 为数组的最终状态。你的目标是执行上述操作尽可能少的次数，使得 $a'_1 \,\&\, a'_2 \,\&\, \ldots \,\&\, a'_n = X$。其中 $\&$ 表示按位与运算。

共有 $q$ 个这样的查询整数 $X$：$X_1, X_2, \ldots, X_q$。请对每个 $X = X_i$ 计算对应的答案。注意：所有查询均独立处理，且均从相同的初始数组 $a$ 出发。

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}$).

第一行包含两个整数 $n$ 和 $q$（$2 \le n \le 200\,000$，$1 \le q \le 200\,000$）—— 分别表示数组的长度和查询次数。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（对每个 $i$，满足 $0 \le a_i \lt 2^{20}$）。

接下来的 $q$ 行每行包含一个整数 $X_i$（$0 \le X_i \lt 2^{20}$）。

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.

对于 $q$ 个查询中的每一个查询 $i$，输出使得数组 $a'$ 满足 $a'_1 \,\&\, a'_2 \,\&\, \ldots \,\&\, a'_n = X_i$ 所需的最少操作次数。

可以证明，总能在有限次操作内得到满足条件的数组 $a'$。

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

对于第一个查询，你可以将 $i = 3$（即 $a_i = 7$）增加，得到数组 $a = [6, 4, 8, 5, 4]$，此时 $6 \,\&\, 4 \,\&\, 8 \,\&\, 5 \,\&\, 4 = 0$。

对于第三个查询，原数组已满足条件：$6 \,\&\, 4 \,\&\, 7 \,\&\, 5 \,\&\, 4 = 4$。