20463번 - Иллюзия сортировки 서브태스크다국어

Известный программист пробует себя в роли иллюзиониста. Его коронный фокус состоит в следующем.

Для заданного массива из $n$ целых неотрицательных чисел $a_1, a_2, \ldots a_n$ он быстро подбирает магическое число $b$. Целое неотрицательное число $b$ называется магическим для массива, если применение операции побитового исключающего ИЛИ с этим числом к каждому элементу массива превращает его в отсортированный массив. Иначе говоря, \[ (a_1 \oplus b) \leq (a_2 \oplus b) \leq \ldots \leq (a_n \oplus b), \] где $\oplus$ --- операция побитового исключающего ИЛИ.

Чтобы фокус был более эффектным, после предъявления магического числа для заданного массива иллюзионист $q$ раз выполняет следующее действие. Он предлагает зрителям изменить один из элементов массива и после этого снова пытается предъявить магическое число. При этом программист настолько отточил свое мастерство иллюзиониста, что каждый раз предъявляет зрителям минимальное возможное магическое число. Иногда фокус не удаётся, так как для полученного массива невозможно подобрать магическое число.

Требуется написать программу, которая по заданному исходно массиву, а также после каждого изменения элемента, вычисляет минимальное магическое число для полученного массива, либо определяет, что такого числа нет.

Первая строка входных данных содержит целое число $n$ --- количество чисел в массиве ($1 \leq n \leq 10^6$).

Вторая строка содержит $n$ целых чисел $a_1, a_2, \ldots, a_n$ --- элементы массива ($0 \leq a_i < 2^{30}$).

Третья строка содержит целое число $q$ --- число изменений элемента массива ($0 \leq q \leq 10^6$).

Следующие $q$ строк содержат по два целых числа $p_i$ и $v_i$, где $p_i$ --- номер элемента массива, который следует заменить ($1 \le p_i \le n$), а $v_i$ --- новое значение этого элемента ($0 \le v_i < 2^{30}$).

Выходные данные должны содержать $(q + 1)$ целых чисел $b_0, b_1, \ldots, b_q$, по одному в строке. 

Значение $b_0$ --- либо минимальное возможное магическое число для исходного массива, либо $-1$, если такого числа не существует. 

Для $i$ от 1 до $q$ значение $b_i$ --- либо минимальное возможное магическое число для массива после первых $i$ изменений, либо $-1$, если такого числа не существует.

Исключающее ИЛИ --- это логическая операция, обозначамая знаком $\oplus$, которая задаётся следующей таблицей истинности:

Определим побитовое исключающее ИЛИ для двух неотрицательных целых чисел $x$ и $y$. Запишем каждое из целых чисел $x$ и $y$ в двоичной системе счисления, дополнив при необходимости более короткое из чисел ведущими нулями до равной длины. Побитовое исключающее ИЛИ двух целых чисел $x$ и $y$, обозначаемое также как $x \oplus y$, это целое неотрицательное число, каждый разряд которого в двоичной системе счисления является исключающим ИЛИ соответствующих разрядов чисел $x$ и $y$. Например, $5 \oplus 22 = 101_2 \oplus 10110_2 = 10011_2 = 19$.

Среди предложенных на олимпиаде языков программирования в языке Паскаль для обозначения исключающего ИЛИ используется оператор <<xor>>, в остальных языках программирования используется оператор <<^>>.