← 返回题目列表

Codeforces · 1658/D2

D2. 388535(硬版)

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

这是问题的困难版本。两个版本之间的约束差异在下面用红色标出。只有当问题的所有版本都得到解决后,你才能进行黑客攻击。

马林和五条正在用阵玩捉迷藏。

Gojou 最初执行以下步骤:

- 首先,Gojou 选择 $$$2$$$ 整数 $$$l$$$ 和 $$$r$$$ 使得 $$$l \leq r$$$。
- 然后,Gojou 将创建一个长度为 $$$r-l+1$$$ 的数组 $$$a$$$,它是数组 $$$[l,l+1,\ldots,r]$$$ 的排列。
- 最后,Gojou 选择一个秘密整数 $$$x$$$ 并将所有 $$$i$$$ 的 $$$a_i$$$ 设置为 $$$a_i \oplus x$$$ (其中 $$$\oplus$$$ 表示按位异或运算)。

然后,Marin 被赋予 $$$l,r$$$ 的值和最终数组 $$$a$$$。她需要找到秘密整数 $$$x$$$ 才能获胜。你能帮助她吗?

请注意,Gojou 可能会选择多个可能的 $$$x$$$。 Marin 可以找到任何可能产生 $$$a$$$ 最终值的 $$$x$$$。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^5$$$) — 测试用例的数量。

每个测试用例的第一行包含两个整数 $$$l$$$ 和 $$$r$$$ ($$$\color{red}{\boldsymbol{0} \boldsymbol{\le} \boldsymbol{l}} \le r < 2^{17}$$$)。

第二行包含 $$$r - l + 1$$$ 空格分隔的整数 $$$a_1,a_2,\ldots,a_{r-l+1}$$$ ($$$0 \le a_i < 2^{17}$$$)。保证数组 $$$a$$$ 有效。

保证所有测试用例的 $$$r - l + 1$$$ 之和不超过 $$$2^{17}$$$。

输出

对于每个测试用例,打印一个整数 $$$x$$$。如果有多个答案,请打印其中一个。

示例

输入 #1

3
4 7
3 2 1 0
4 7
4 7 6 5
1 3
0 2 1

输出 #1

4
0
3

注意

在第一个测试用例中,原始数组是 $$$[7, 6, 5, 4]$$$。

在第二个测试用例中,原始数组是$$$[4, 7, 6, 5]$$$。

在第三个测试用例中,原始数组是$$$[3, 1, 2]$$$。