Задача №113545. Иллюзия сортировки
Известный программист пробует себя в роли иллюзиониста. Его коронный фокус состоит в следующем.
Для заданного массива из n целых неотрицательных чисел a1, a2, ..., an он быстро подбирает магическое число b. Целое неотрицательное число b называется магическим для массива, если применение операции побитового исключающего ИЛИ с этим числом к каждому элементу массива превращает его в отсортированный массив. Иначе говоря,
\(\) (a_1\oplus b) \le (a_2\oplus b) \le ... \le (a_n\oplus b) \(\)где \(\oplus\) — операция побитового исключающего ИЛИ.
Чтобы фокус был более эффектным, после предъявления магического числа для заданного массива иллюзионист q раз выполняет следующее действие. Он предлагает зрителям изменить один из элементов массива и после этого снова пытается предъявить магическое число. При этом программист настолько отточил свое мастерство иллюзиониста, что каждый раз предъявляет зрителям минимальное возможное магическое число. Иногда фокус не удаётся, так как для полученного массива невозможно подобрать магическое число.
Требуется написать программу, которая по заданному исходно массиву, а также после каждого изменения элемента, вычисляет минимальное магическое число для полученного массива, либо определяет, что такого числа нет.
Исключающее ИЛИ — это логическая операция, обозначаемая знаком \(\oplus\), которая задаётся следующей таблицей истинности:
Определим побитовое исключающее ИЛИ для двух неотрицательных целых чисел x и y. Запишем каждое из целых чисел x и y в двоичной системе счисления, дополнив при необходимости более короткое из чисел ведущими нулями до равной длины. Побитовое исключающее ИЛИ двух целых чисел \(x\) и \(y\), обозначаемое также как \(\oplus\), это целое неотрицательное число, каждый разряд которого в двоичной системе счисления является исключающим ИЛИ соответствующих разрядов чисел \(x\) и \(y\). Например, \(5\oplus22=101_2\oplus10110_2=10011_2=19\).
Среди предложенных на олимпиаде языков программирования в языке Паскаль для обозначения исключающего ИЛИ используется оператор «xor», в остальных языках программирования используется оператор «^».
Первая строка входных данных содержит целое число n — количество чисел в массиве (1 ≤ n ≤ 106).
Вторая строка содержит n целых чисел a1, a2, ..., an — элементы массива (0 ≤ ai < 230).
Третья строка содержит целое число q — число изменений элемента массива (0 ≤ q ≤ 106).
Следующие q строк содержат по два целых числа pi и vi, где pi — номер элемента массива, который следует заменить (1 ≤ pi ≤ n), а vi — новое значение этого элемента (0 ≤ vi < 230).
Выходные данные должны содержать (q + 1) целых чисел b0, b1, ..., bq, по одному в строке.
Значение b0 — либо минимальное возможное магическое число для исходного массива, либо - 1, если такого числа не существует.
Для i от 1 до q значение bi — либо минимальное возможное магическое число для массива после первых i изменений, либо - 1, если такого числа не существует.
3 0 1 4 3 2 7 3 3 1 4
0 2 -1 4