Это усложненная версия этой задачи. Различия между ограничениями в версиях выделены красным цветом. Вы можете совершать взломы, только если решили обе версии.
Марин и Годзё играют в прятки с массивом.
Сначала Годзё выполняет следующую последовательность действий:
- Во-первых, Годзё выбирает \(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\).
Выходные данные
Для каждого набора входных данных выведите \(x\). Если ответов несколько, то выведите любой из них.
Примечание
В первом примере начальное значение массива имеет вид \([7, 6, 5, 4]\).
Во втором примере начальное значение массива имеет вид \([4, 7, 6, 5]\).
В третьем примере начальное значение массива имеет вид \([3, 1, 2]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
4 7
3 2 1 0
4 7
4 7 6 5
1 3
0 2 1
|
4
0
3
|