有一个整数数组 $$$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$$$ 单独且独立地处理的。
输入
第一行包含整数 $$$n$$$ 和 $$$q$$$ ($$$2 \le n \le 200\,000$$$, $$$1 \le q \le 200\,000$$$) - 数组的长度和查询的数量。
第二行包含整数 $$$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}$$$)。
输出
对于 $$$q$$$ 中的每个查询 $$$i$$$,打印到达数组 $$$a'$$$ 的最小操作数,使得 $$$a'_1 \,\&\, a'_2 \,\&\, \ldots \,\&\, a'_n = X_i$$$。
可以证明,在有限次数的操作中总是可以获得这样的数组$$$a'$$$。
示例
输入复制
5 46 4 7 5 40246
输出复制
1 8 0 5
注意
对于第一个查询,可以增加 $$$i = 3$$$ ($$$a_i = 7$$$) 并得到数组 $$$a = [6, 4, 8, 5, 4]$$$,然后 $$$6 \,\&\, 4 \,\&\, 8 \,\&\, 5 \,\&\, 4 = 0$$$。
对于第三个查询,原始数组已匹配条件:$$$6 \,\&\, 4 \,\&\, 7 \,\&\, 5 \,\&\, 4 = 4$$$。