#2767. 「ROI 2017 Day 1」排序幻觉

内存限制:512 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:Special Judge
上传者: Planet6174

题目描述

题目译自 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

数据范围与提示

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