一位著名的程序员正在尝试扮演魔术师的角色。他的拿手戏法如下：

对于给定的包含 $n$ 个非负整数的数组 $a_1, a_2, \dots, a_n$，他能迅速找到一个“魔法数” $b$。如果对数组中的每个元素执行按位异或运算（$\oplus$）后，数组变为有序，则称非负整数 $b$ 为该数组的魔法数。换句话说：

$$(a_1 \oplus b) \leqslant (a_2 \oplus b) \leqslant \dots \leqslant (a_n \oplus b)$$

其中 $\oplus$ 表示按位异或运算。

为了让戏法更具观赏性，在展示了初始数组的魔法数后，魔术师会进行 $q$ 次操作。每次操作中，他会邀请观众修改数组中的一个元素，随后再次尝试展示魔法数。这位程序员已经将他的魔术技巧磨练得炉火纯青，每次都能向观众展示出最小的可能魔法数。有时戏法会失败，因为对于修改后的数组，可能不存在任何魔法数。

你需要编写一个程序，计算给定初始数组以及每次修改元素后，该数组对应的最小魔法数；如果不存在这样的数，则输出 $-1$。

说明

按位异或是一种逻辑运算，用符号 $\oplus$ 表示，其真值表如下：

对于两个非负整数 $x$ 和 $y$，按位异或运算定义如下：将 $x$ 和 $y$ 写成二进制形式，必要时在较短的数前补前导零，使其长度相等。两个整数 $x$ 和 $y$ 的按位异或（记作 $x \oplus y$）是一个非负整数，其二进制表示中的每一位都是对应位进行按位异或的结果。例如，$5 \oplus 22 = 101_2 \oplus 10110_2 = 10011_2 = 19$。

在竞赛提供的编程语言中，Pascal 使用 xor 运算符，其他编程语言使用 ^ 运算符。

输入格式

第一行包含一个整数 $n$ —— 数组中数字的个数 ($1 \leqslant n \leqslant 10^6$)。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ —— 数组元素 ($0 \leqslant a_i < 2^{30}$)。

第三行包含一个整数 $q$ —— 修改数组元素的次数 ($0 \leqslant q \leqslant 10^6$)。

接下来的 $q$ 行，每行包含两个整数 $p_i$ 和 $v_i$，其中 $p_i$ 是要修改的数组元素下标 ($1 \leqslant p_i \leqslant n$)，$v_i$ 是该元素的新值 ($0 \leqslant v_i < 2^{30}$)。

输出格式

输出应包含 $(q + 1)$ 个整数 $b_0, b_1, \dots, b_q$，每行一个。

$b_0$ 为初始数组的最小可能魔法数，若不存在则为 $-1$。

对于从 $1$ 到 $q$ 的每个 $i$，$b_i$ 为经过前 $i$ 次修改后数组的最小可能魔法数，若不存在则为 $-1$。

样例

输入 1

3
0 1 4
3
2 7
3 3
1 4

输出 1

0
2
-1
4

子任务