CF1658D2.388535 (Hard Version)

This is the hard version of the problem. The difference in the constraints between both versions are colored below in red. You can make hacks only if all versions of the problem are solved.

Marin and Gojou are playing hide-and-seek with an array.

Gojou initially perform the following steps:

• First, Gojou chooses $2$ integers $l$ and $r$ such that $l \leq r$.
• Then, Gojou will make an array $a$ of length $r-l+1$ which is a permutation of the array $[l,l+1,\ldots,r]$.
• Finally, Gojou chooses a secret integer $x$ and sets $a_i$ to $a_i \oplus x$ for all $i$ (where $\oplus$ denotes the bitwise XOR operation).

Marin is then given the values of $l,r$ and the final array $a$. She needs to find the secret integer $x$ to win. Can you help her?

Note that there may be multiple possible $x$ that Gojou could have chosen. Marin can find any possible $x$ that could have resulted in the final value of $a$.

这是该问题的困难版本。两个版本在约束条件上的区别已在下方用红色标出。仅当该问题的所有版本均被解决时，你才可以进行 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$ 表示按位异或运算）。

随后，Marin 被给出 $l$、$r$ 和最终的数组 $a$。她需要找出秘密整数 $x$ 才能获胜。你能帮她吗？

注意：可能存在多个 Gojou 可能选择的 $x$。Marin 只需找出任意一个能导致最终数组 $a$ 的可能的 $x$ 即可。

The first line contains a single integer $t$ ($1 \leq t \leq 10^5$) — the number of test cases.

In the first line of each test case contains two integers $l$ and $r$ ($\color{red}{\boldsymbol{0} \boldsymbol{\le} \boldsymbol{l}} \le r \lt 2^{17}$).

The second line contains $r - l + 1$ space-seperated integers of $a_1,a_2,\ldots,a_{r-l+1}$ ($0 \le a_i \lt 2^{17}$). It is guaranteed that array $a$ is valid.

It is guaranteed that the sum of $r - l + 1$ over all test cases does not exceed $2^{17}$.

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

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

第二行包含 $r - l + 1$ 个由空格分隔的整数 $a_1,a_2,\ldots,a_{r-l+1}$（$0 \le a_i \lt 2^{17}$）。保证数组 $a$ 是合法的。

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

For each test case print an integer $x$. If there are multiple answers, print any.

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

In the first test case, the original array is $[7, 6, 5, 4]$.

In the second test case, the original array is $[4, 7, 6, 5]$.

In the third test case, the original array is $[3, 1, 2]$.

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

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

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