这是问题的简单版本。两个版本之间的唯一区别是对 $$$n$$$ 和 $$$q$$$ 的约束、内存和时间限制。只有当问题的所有版本都得到解决后,你才能进行黑客攻击。
Theofanis 非常喜欢玩弄数字。他有一个大小为 $$$n$$$ 的数组 $$$a$$$ 和一个整数 $$$k$$$。他最多可以在数组中进行 $$$k$$$ 操作。在每次操作中,他选择一个元素并将其增加 $$$1$$$。
他找到了数组 $$$a$$$ 在最多 $$$k$$$ 操作后可以拥有的最大按位 AND。
Theofanis 投入了大量的工作来寻找这个值,并且对他的结果非常满意。不幸的是,Adaś 是个邪恶的人,他决定通过反复改变 $$$k$$$ 的值来欺负他。
通过计算 $$$q$$$ 不同 $$$k$$$ 值的最大可能按位 AND 来帮助 Theofanis。请注意,查询是独立的。
输入
第一行包含两个整数 $$$n$$$ 和 $$$q$$$ ($$$1 \le n, q \le 10^5$$$ 和 $$$n \cdot q \le 10^5$$$) - 数组的大小和查询的数量。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 10^6$$$) — 数组的元素。
接下来的 $$$q$$$ 行描述查询。第 $$$i$$$ 行包含一个整数 $$$k_i$$$ ($$$0 \le k_i \le 10^{18}$$$) - 第 $$$i$$$ 查询中可以完成的操作数。
输出
对于每个查询,打印一个整数 - 数组 $$$a$$$ 在最多 $$$k_i$$$ 操作后可以拥有的最大按位 AND。
示例
输入 #1
4 2 1 3 7 5 2 10
输出 #1
2 6
输入 #2
3 5 4 0 2 9 8 17 1 3
输出 #2
5 4 7 0 1
输入 #3
1 2 10 5 2318381298321
输出 #3
15 2318381298331
注意
在第一个测试用例中,在第一个查询中,我们在数组的第一个和最后一个元素中添加 $$$1$$$ 。
因此,数组变为 $$$[2,3,7,6]$$$,按位 AND 等于 $$$2$$$。
在第二个测试用例中,在第一个查询中,我们在第一个元素中添加 $$$1$$$,在第二个元素中添加 $$$5$$$,在第三个元素中添加 $$$3$$$,现在所有元素都等于 $$$5$$$。