设 $$$\mathsf{AND}$$$ 表示按位 AND 运算,$$$\mathsf{OR}$$$ 表示按位 OR 运算。
给定一个长度为 $$$n$$$ 的数组 $$$a$$$ 和一个非负整数 $$$k$$$。您最多可以对以下类型的数组执行 $$$k$$$ 操作:
- 选择索引 $$$i$$$ ($$$1 \leq i \leq n$$$) 并将 $$$a_i$$$ 替换为 $$$a_i$$$ $$$\mathsf{OR}$$$ $$$2^j$$$,其中 $$$j$$$ 是 $$$0$$$ 到 $$$30$$$ 之间的任何整数(含)。换句话说,在操作中,您可以选择索引 $$$i$$$ ($$$1 \leq i \leq n$$$) 并将 $$$a_i$$$ 的第 $$$j$$$ 位设置为 $$$1$$$ ($$$0 \leq j \leq 30$$$)。
执行最多 $$$k$$$ 运算后,输出 $$$a_1$$$ $$$\mathsf{AND}$$$ $$$a_2$$$ $$$\mathsf{AND}$$$ $$$\dots$$$ $$$\mathsf{AND}$$$ $$$a_n$$$ 的最大可能值。
输入
输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 100$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$0 \le k \le 10^9$$$)。
接下来是一行,包含描述数组 $$$a$$$ 的 $$$n$$$ 整数 ($$$0 \leq a_i < 2^{31}$$$)。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,输出一行,其中包含 $$$a_1$$$ 的最大可能 $$$\mathsf{AND}$$$ 值 $$$\mathsf{AND}$$$ $$$a_2$$$ $$$\mathsf{AND}$$$ $$$\dots$$$ $$$\mathsf{AND}$$$ $$$a_n$$$ 执行最多 $$$k$$$ 操作后。
示例
输入 #1
4 3 2 2 1 1 7 0 4 6 6 28 6 6 12 1 30 0 4 4 3 1 3 1
输出 #1
2 4 2147483646 1073741825
注意
对于第一个测试用例,我们可以使用 $$$2$$$ 操作设置最后 $$$2$$$ 元素的位 $$$1$$$ ($$$2^1$$$),从而获得数组 [$$$2$$$, $$$3$$$, $$$3$$$],其 $$$\mathsf{AND}$$$ 值等于$$$2$$$。
对于第二个测试用例,我们无法执行任何操作,因此答案只是整个数组的 $$$\mathsf{AND}$$$,即 $$$4$$$。