D2. 388535 (усложненная версия)
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это усложненная версия этой задачи. Различия между ограничениями в версиях выделены красным цветом. Вы можете совершать взломы, только если решили обе версии.

Марин и Годзё играют в прятки с массивом.

Сначала Годзё выполняет следующую последовательность действий:

  • Во-первых, Годзё выбирает $$$2$$$ целых числа $$$l$$$ и $$$r$$$ такие, что $$$l \leq r$$$.
  • Затем Годзё составляет массив $$$a$$$ длины $$$r-l+1$$$, который является перестановкой массива $$$[l,l+1,\ldots,r]$$$.
  • Наконец, Годзё выбирает секретное целое число $$$x$$$ и присваивает в элемент $$$a_i$$$ значение $$$a_i \oplus x$$$ для всех $$$i$$$, где $$$\oplus$$$ обозначает операцию побитового исключающего ИЛИ.

Марин даются значения $$$l,r$$$ и финальный массив $$$a$$$. Её цель — найти секретное число $$$x$$$. Можете ли вы помочь Марин?

Заметим, что значение $$$x$$$ не всегда можно определить однозначно. В этом случае найдите любое возможное $$$x$$$, которое приводит к заданному финальному значению массива $$$a$$$.

Входные данные

В первой строке находится целое число $$$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$$$. Если ответов несколько, то выведите любой из них.

Пример
Входные данные
3
4 7
3 2 1 0
4 7
4 7 6 5
1 3
0 2 1
Выходные данные
4
0
3
Примечание

В первом примере начальное значение массива имеет вид $$$[7, 6, 5, 4]$$$.

Во втором примере начальное значение массива имеет вид $$$[4, 7, 6, 5]$$$.

В третьем примере начальное значение массива имеет вид $$$[3, 1, 2]$$$.