题目描述

题目译自 ROI 2017 Day 1 T2. Иллюзия сортировки

给一个数组 $a[1], a[2], \ldots, a[n]$，选择一个数 $b$，如果 $b$ 满足

$$(a[1] ⊕ b) ≤ (a[2] ⊕ b) ≤ . . . ≤ (a[n] ⊕ b)$$

则称 $b$ 是数组 $a$ 的幻数。此处 $⊕$ 表示按位异或。
该数组将会被先后修改 $q$ 次，我们每次只修改一个数。
第一次修改前以及每次修改后，请给出当前数组最小的幻数，如果当前数组不存在幻数请输出 $-1$。

输入格式

第一行有一个整数 $n$。
第二行有 $n$ 个整数，表示数组 $a$。
第三行有一个整数 $q$。
在接下来的 $q$ 行中，每行有两个整数 $p_i, v_i$，表示将 $a[p_i]$ 修改为 $v_i$。

输出格式

共 $(q+1)$ 行，每行一个整数，表示当前数组最小的幻数。

样例

3
0 1 4
3
2 7
3 3
1 4

0
2
-1
4

数据范围与提示