Problem Description

Given an integer sequence $a$ of length $n$, if an integer $b$ satisfies:

$$(a_1 \operatorname{xor} b) \le (a_2 \operatorname{xor} b) \le \dots \le (a_n \operatorname{xor} b)$$

then $b$ is called a magic number of the sequence $a$.

Next, there are $q$ modifications. In each modification, one number $a_{u_i}$ is changed to an integer $k_i$. Each modification affects the queries that follow. You need to find the smallest magic number of the sequence before the first modification and after each modification. In particular, if no magic number exists, output $-1$.

Input Format

The first line contains an integer $n$, indicating the length of the sequence.

The second line contains $n$ integers, representing the integer sequence $a$.

The third line contains an integer $q$, indicating the number of queries.

The next $q$ lines each contain two integers $u_i$ and $k_i$, meaning that $a_{u_i}$ is modified to $k_i$.

Output Format

Output a total of $(q + 1)$ lines. Each line contains one integer, representing the smallest magic number of the current sequence. If there is no magic number, output $-1$.

3
0 1 4
3
2 7
3 3
1 4

0
2
-1
4

Hint

Constraints

Subtask ID	Score	$1 \le n \le$	$1 \le q \le$	$0 \le a_i, k_i \le$
$1$	$30$	$500$		$2^9$
$2$	$29$	$10^3$		$2^{30}$
$3$	$21$	$10^5$
$4$	$30$	$10^6$

Translated by ChatGPT 5