CF1658D2 388535 (Hard Version)

这是该问题的困难版本。两种版本之间的约束条件差异已在下文用红色标注。只有在所有版本都被解决的情况下，才能进行 hack。 Marin 和 Gojou 正在用一个数组玩捉迷藏游戏。 Gojou 最初会执行以下步骤： - 首先，Gojou 选择两个整数 $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$ 表示[按位异或运算](https://en.wikipedia.org/wiki/Bitwise_operation#XOR)）。 随后，Marin 得到 $l$、$r$ 和最终的数组 $a$。她需要找出秘密整数 $x$ 才能获胜。你能帮她吗？ 注意，可能存在多个 $x$ 使得 Gojou 能得到最终的 $a$。Marin 只需找出任意一个可能的 $x$ 即可。

第一行包含一个整数 $t$（$1 \leq t \leq 10^5$），表示测试用例的数量。 每个测试用例的第一行包含两个整数 $l$ 和 $r$（$\color{red}{\boldsymbol{0} \leq \boldsymbol{l}} \leq r < 2^{17}$）。 第二行包含 $r-l+1$ 个用空格分隔的整数 $a_1, a_2, \ldots, a_{r-l+1}$（$0 \leq a_i < 2^{17}$）。保证数组 $a$ 是有效的。 保证所有测试用例中 $r-l+1$ 的总和不超过 $2^{17}$。

对于每个测试用例，输出一个整数 $x$。如果有多个答案，输出任意一个均可。

在第一个测试用例中，原始数组为 $[7, 6, 5, 4]$。 在第二个测试用例中，原始数组为 $[4, 7, 6, 5]$。 在第三个测试用例中，原始数组为 $[3, 1, 2]$。 由 ChatGPT 4.1 翻译