这是问题的困难版本。两个版本之间的约束差异在下面用红色标出。只有当问题的所有版本都得到解决后,你才能进行黑客攻击。
马林和五条正在用阵玩捉迷藏。
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]$$$。