该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Background

Special for beginners, ^_^

Description

都知道 $3>2>1$ ，但是如果异或同一个数后，原数组就会满足升序排列。

现在，你作为国王的得利奸臣，就是要找到一个最小的自然数，使得原来的数组异或该数后，满足升序排列，如果实在抄不到，则输出 $-1$ 。

接下来有 $q$ 次修改，每次修改一个数 $a_{u_i}$ 为整数 $k_i$，每次修改都会对后面的询问产生影响。请你求出第一次修改前以及每次修改后这个数列的最小的异或数是多少，如果不存在请输出 $-1$ 。

Format

Input

第一行一个整数 $n$ 表示数列长度。

第二行 $n$ 个整数表示整数数列 $a$。

第三行一个整数 $q$ 表示询问次数。

接下来 $q$ 行每行两个整数 $u_i,k_i$，表示将 $a_{u_i}$ 修改为 $k_i$。

Output

共 $(q+1)$ 行，每行一个整数表示当前数列最小的异或数，如果没有请输出 $-1$。

Samples

3
3 2 1
3
1 1
1 2
1 3

3
-1
2
3

Limitation

1s, 1024KiB for each test case.