← 返回题目列表

Codeforces · 1696/A

A. 尼特orz!

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

NIT,切肉刀,是城里的新东西!成千上万的人排队等着orz他。为了让他的 orzers 开心,NIT 决定让他们解决以下与 $$$\operatorname{or} z$$$ 相关的问题。你也能解决这个问题吗?

给定一个由 $$$n$$$ 整数、$$$a$$$ 和整数 $$$z$$$ 组成的 1 索引数组。您可以执行以下操作任意次数(可能为零):

- 选择一个正整数 $$$i$$$,使得 $$$1\le i\le n$$$。然后,同时将 $$$a_i$$$ 设置为 $$$(a_i\operatorname{or} z)$$$ 并将 $$$z$$$ 设置为 $$$(a_i\operatorname{and} z)$$$。换句话说,令$$$x$$$和$$$y$$$分别为$$$a_i$$$和$$$z$$$的当前值。然后将 $$$a_i$$$ 设置为 $$$(x\operatorname{or}y)$$$,并将 $$$z$$$ 设置为 $$$(x\operatorname{and}y)$$$。

这里 $$$\operatorname{or}$$$ 和 $$$\operatorname{and}$$$ 分别表示按位运算 OR 和 AND。

在任意次数(可能为零)的运算后,找出 $$$a$$$ 中最大值的最大可能值。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 100$$$)。测试用例的描述如下。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$z$$$ ($$$1\le n\le 2000$$$, $$$0\le z<2^{30}$$$)。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1$$$,$$$a_2$$$,$$$\ldots$$$,$$$a_n$$$ ($$$0\le a_i<2^{30}$$$)。

保证所有测试用例的$$$n$$$总和不超过$$$10^4$$$。

输出

对于每个测试用例,打印一个整数 - 问题的答案。

示例

输入 #1

5
2 3
3 4
5 5
0 2 4 6 8
1 9
10
5 7
7 15 30 29 27
3 39548743
10293834 10284344 13635445

输出 #1

7
13
11
31
48234367

注意

在示例的第一个测试用例中,一个最佳操作顺序是:

- 使用 $$$i=1$$$ 进行运算。现在 $$$a_1$$$ 变为 $$$(3\operatorname{or}3)=3$$$,$$$z$$$ 变为 $$$(3\operatorname{and}3)=3$$$。
- 使用 $$$i=2$$$ 进行运算。现在 $$$a_2$$$ 变为 $$$(4\operatorname{or}3)=7$$$,$$$z$$$ 变为 $$$(4\operatorname{and}3)=0$$$。
- 使用 $$$i=1$$$ 进行运算。现在 $$$a_1$$$ 变为 $$$(3\operatorname{or}0)=3$$$,$$$z$$$ 变为 $$$(3\operatorname{and}0)=0$$$。

经过这些操作,序列$$$a$$$变为$$$[3,7]$$$,其中的最大值为$$$7$$$。我们可以证明$$$a$$$中的最大值永远不会超过$$$7$$$,所以答案是$$$7$$$。

在示例的第四个测试用例中,一个最佳操作顺序是:

- 使用 $$$i=1$$$ 进行运算。现在 $$$a_1$$$ 变为 $$$(7\operatorname{or}7)=7$$$,$$$z$$$ 变为 $$$(7\operatorname{and}7)=7$$$。
- 使用 $$$i=3$$$ 进行运算。现在 $$$a_3$$$ 变为 $$$(30\operatorname{or}7)=31$$$,$$$z$$$ 变为 $$$(30\operatorname{and}7)=6$$$。
- 使用 $$$i=5$$$ 进行运算。现在 $$$a_5$$$ 变为 $$$(27\operatorname{or}6)=31$$$,$$$z$$$ 变为 $$$(27\operatorname{and}6)=2$$$。