A famous programmer is trying their hand at being a magician. Their signature trick is as follows.

For a given array of $n$ non-negative integers $a_1, a_2, \dots, a_n$, they quickly find a "magic number" $b$. A non-negative integer $b$ is called magic for an array if applying the bitwise exclusive OR operation with this number to each element of the array transforms it into a sorted array. In other words,

$$(a_1 \oplus b) \leqslant (a_2 \oplus b) \leqslant \dots \leqslant (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. They invite the audience to change one of the elements of the array, and after that, they try to present a magic number again. The programmer has honed their skills so much that they always present the smallest possible magic number to the audience. Sometimes the trick fails because it is impossible to find a magic number for the resulting array.

You are required to write a program that, given the initial array and each subsequent element change, calculates the minimum magic number for the resulting array, or determines that no such number exists.

Note

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

We define the bitwise exclusive OR for two non-negative integers $x$ and $y$. Write each of the integers $x$ and $y$ in binary representation, padding the shorter number with leading zeros to equal length if necessary. The bitwise exclusive OR of two integers $x$ and $y$, also denoted as $x \oplus y$, is a non-negative integer whose every bit in binary representation is the exclusive OR of the corresponding bits 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, the Pascal language uses the "xor" operator for exclusive OR, while other programming languages use the "^" operator.

Input

The first line of input contains an integer $n$ — the number of integers in the array ($1 \leqslant n \leqslant 10^6$).

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

The third line contains an integer $q$ — the number of element changes ($0 \leqslant q \leqslant 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 be replaced ($1 \leqslant p_i \leqslant n$), and $v_i$ is the new value of this element ($0 \leqslant v_i < 2^{30}$).

Output

The output must contain $(q + 1)$ integers $b_0, b_1, \dots, 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.

Examples

Input 1

3
0 1 4
3
2 7
3 3
1 4

Output 1

0
2
-1
4

Subtasks