给你一个 $$$n$$$ 非负整数数组。
您想要回答给定的 $$$q$$$ 独立场景。第$$$i$$$场景下,允许执行以下操作 最多 $$$b_i$$$ 次:
- 选择数组的一个元素并将其增加$$$1$$$。
您的目标是在数组中所有数字的按位或中,最大化等于 $$$1$$$ 的位数。找到每个场景的这个数字。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^3$$$)。测试用例的描述如下。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$q$$$ ($$$1 \leq n, q \leq 10^{5}$$$) - 数组的大小和场景的数量。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i \leq 10^{9}$$$) — 数组的元素。
接下来的 $$$q$$$ 行中的第 $$$i$$$ 行包含一个整数 $$$b_i$$$ ($$$0 \leq b_i \leq 10^{9}$$$) — 第 $$$i$$$ 场景中允许的最大操作数。
保证所有测试用例的$$$n$$$总和不超过$$$10^{5}$$$,所有测试用例的$$$q$$$总和不超过$$$10^{5}$$$。
输出
对于每个测试用例,输出 $$$q$$$ 行,其中第 $$$i$$$ 包含单个整数 - 在第 $$$i$$$ 场景中按位或中的最大可能位数等于 $$$1$$$。
示例
输入复制
31 300242 21 3032 11000000000 10000000001000000000
输出复制
0122331
注意
展示台链接
在第一个测试用例中:
- 在第一种情况下,我们没有任何操作,因此答案等于原始数组 $$$0$$$ 的按位 OR 中 $$$1$$$ 位的数量,该数组在其二进制表示中设置了 $$$0$$$ 位。
- 在第二种情况下,在按位 OR 中实现 $$$1$$$ 位设置的一种方法是将 $$$a_1$$$ 增加 $$$1$$$ 两次,获得 $$$2={(10)}_2$$$ 的按位 OR。可以证明,这是我们最多执行两次操作可以获得的最佳值。
- 在第三个场景中,实现 $$$2$$$ 结果的一种方法是将 $$$1$$$ 与 $$$a_1$$$ 相加三次,这可以证明是最佳的。请注意,您不必应用操作 $$$4$$$ 次。
在第二个测试用例中:
- 在第一种情况下,我们没有任何操作,因此答案等于原始数组按位或中的 $$$1$$$ 位的数量,即 $$$2$$$。
- 在第二种情况下,实现 $$$3$$$ 结果的一种方法是将 $$$1$$$ 添加到 $$$a_2$$$ 三次,这可以证明是最佳的。