Xorcisten

Xorcisten Roxanne has a remarkable ability: she can sort lists very quickly. Given a list of integers $a_1, a_2, \dots, a_N$, she instantly finds an integer $X$ such that

$a_1 \oplus X \leq a_2 \oplus X \leq \dots \leq a_N \oplus X$

Here $\oplus$ is bitwise XOR. Write both numbers in binary. Going from the least significant digit upward, write 0 if the two digits are equal and 1 otherwise. This is the same as adding the numbers in binary without carries.

All she has to do next is replace each $a_i$ with $a_i \oplus x$, and the list is sorted.

Several companies often hire Roxanne to sort their very long lists. One day, however, she discovers that her ability is gone. Your task is to write a program so that she can keep her job.

You are given a list of non-negative integers $a_1, \dots, a_N$ and $Q$ updates $p_i, v_i$, meaning that $a_{p_i}$ changes to $v_i$. Let $c_i$ be the smallest non-negative integer $X$ such that the list $a_1 \oplus X, \dots, a_N \oplus X$ is sorted after the first $i$ updates have been applied. Print $c_0, c_1, \dots, c_Q$. If no such $X$ exists, print $-1$ for that value.

The first line contains an integer $N$ ($1 \leq N \leq 10^6$), the number of integers in the list.

The second line contains $N$ integers $a_1, a_2, \dots, a_N$ ($0 \leq a_i < 2^{30}$).

The third line contains an integer $Q$ ($0 \leq Q \leq 10^6$), the number of updates.

Each of the next $Q$ lines contains two integers $p_i$ ($1 \leq p_i \leq N$) and $v_i$ ($0 \leq v_i < 2^{30}$), meaning that $a_{p_i}$ changes to $v_i$.

Print $Q+1$ lines. Line $i$ (counting from 0) contains $c_i$, the smallest possible $x$ that sorts the list after updates $1, 2, \dots, i$ have been applied, or $-1$ if no such $x$ exists.

• $N, Q \leq 10^6$
• $a_i, v_i < 2^{30}$