题目描述

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

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

$$(a[1] \oplus b) \leq (a[2] \oplus b) \leq \cdots \leq (a[n] \oplus b) $$

则称 $b$ 是数组 $a$ 的幻数。此处 $\oplus$ 表示按位异或运算。

该数组将会被先后修改 $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

数据范围与提示

子任务	分值	$n$	$q$	$a[i], v_i$
1	30	$1 \leqslant n \leqslant 500$	$0 \leqslant q \leqslant 500$	$0 \leqslant a[i], v_i \leqslant 2^9$
2	29	$1 \leqslant n \leqslant 1000$	$0 \leqslant q \leqslant 1000$	$0 \leqslant a[i], v_i \leqslant 2^{30}$
3	21	$1 \leqslant n \leqslant 10^5$	$0 \leqslant q \leqslant 10^5$
4	20	$1 \leqslant n \leqslant 10^6$	$0 \leqslant q \leqslant 10^6$