Sorting Illusion

A well-known programmer tries his hand at being a magician. His signature trick works as follows.

Given an array of $n$ non-negative integers $a_1, a_2, \ldots, a_n$, he quickly finds a magic number $b$. A non-negative integer $b$ is called magic for the array if applying the bitwise exclusive OR operation with this number to every element of the array turns the array into a sorted array. In other words, [ (a_1 \oplus b) \leq (a_2 \oplus b) \leq \ldots \leq (a_n \oplus b), ] where $\oplus$ is the bitwise exclusive OR operation.

To make the trick more impressive, after presenting the magic number for the given array, the magician performs the following action $q$ times. He invites the audience to change one of the elements of the array and then tries to present a magic number again. The programmer has honed his magician's skill so well that each time he presents the audience with the smallest possible magic number. Sometimes the trick fails, because no magic number can be found for the resulting array.

Write a program that, for the given initial array and after each change of an element, computes the minimum magic number for the resulting array, or determines that no such number exists.

The first line of the input contains an integer $n$, the number of numbers in the array ($1 \leq n \leq 10^6$).

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$, the elements of the array ($0 \leq a_i < 2^{30}$).

The third line contains an integer $q$, the number of changes to an element of the array ($0 \leq q \leq 10^6$).

The following $q$ lines each contain two integers $p_i$ and $v_i$, where $p_i$ is the index of the array element to replace ($1 \le p_i \le n$) and $v_i$ is the new value of that element ($0 \le v_i < 2^{30}$).

The output must contain $(q + 1)$ integers $b_0, b_1, \ldots, b_q$, one per line.

The value $b_0$ is either the minimum possible magic number for the initial array or $-1$ if no such number exists.

For $i$ from 1 to $q$, the value $b_i$ is either the minimum possible magic number for the array after the first $i$ changes or $-1$ if no such number exists.

Exclusive OR is a logical operation denoted by $\oplus$, defined by the following truth table:

Let us define the bitwise exclusive OR of two non-negative integers $x$ and $y$. Write each of the integers $x$ and $y$ in binary, padding the shorter number with leading zeros if necessary so that they have equal length. The bitwise exclusive OR of two integers $x$ and $y$, also denoted $x \oplus y$, is the non-negative integer whose binary representation has, in each digit, the exclusive OR of the corresponding digits of $x$ and $y$. For example, $5 \oplus 22 = 101_2 \oplus 10110_2 = 10011_2 = 19$.

Among the programming languages offered at the olympiad, Pascal uses the <<xor>> operator to denote exclusive OR, and the remaining programming languages use the <<^>> operator.