← 返回题目列表

Codeforces · 1903/D1

D1. 最大和查询(简易版)

中文机器翻译题面 查看原题

这是问题的简单版本。两个版本之间的唯一区别是对 $$$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$$$。