정렬 환상

한 저명한 프로그래머가 마술사에 도전한다. 그의 대표 마술은 다음과 같다.

$n$개의 음이 아닌 정수 $a_1, a_2, \ldots, a_n$으로 이루어진 배열이 주어지면, 그는 마법의 수 $b$를 재빨리 찾아낸다. 음이 아닌 정수 $b$가 배열에 대해 마법의 수라는 것은, 이 수를 배열의 각 원소에 비트별 배타적 논리합 연산으로 적용했을 때 배열이 정렬된 배열로 바뀐다는 뜻이다. 다시 말해, [ (a_1 \oplus b) \leq (a_2 \oplus b) \leq \ldots \leq (a_n \oplus b), ] 여기서 $\oplus$는 비트별 배타적 논리합 연산이다.

마술을 더 화려하게 만들기 위해, 마법의 수를 보여준 뒤 마술사는 $q$번 다음과 같은 동작을 수행한다. 그는 관객에게 배열의 원소 하나를 바꾸도록 제안하고, 그 뒤 다시 마법의 수를 보여주려 한다. 이때 프로그래머는 마술 솜씨를 너무나 갈고닦았기에 매번 가능한 한 가장 작은 마법의 수를 관객에게 보여준다. 가끔은 마술이 실패한다. 바뀐 배열에서 마법의 수를 찾을 수 없기 때문이다.

주어진 초기 배열에 대해, 그리고 원소를 바꿀 때마다, 얻어진 배열의 최소 마법의 수를 계산하거나 그러한 수가 없음을 판별하는 프로그램을 작성하라.

첫째 줄에는 배열의 수 개수 $n$이 주어진다 ($1 \leq n \leq 10^6$).

둘째 줄에는 배열의 원소 $a_1, a_2, \ldots, a_n$이 주어진다 ($0 \leq a_i < 2^{30}$).

셋째 줄에는 원소를 바꾸는 횟수 $q$가 주어진다 ($0 \leq q \leq 10^6$).

다음 $q$개 줄에는 각각 두 정수 $p_i$와 $v_i$가 주어진다. $p_i$는 바꿀 원소의 번호이고 ($1 \le p_i \le n$), $v_i$는 그 원소의 새 값이다 ($0 \le v_i < 2^{30}$).

출력에는 $(q + 1)$개의 정수 $b_0, b_1, \ldots, b_q$가 한 줄에 하나씩 있어야 한다.

$b_0$은 초기 배열의 가능한 최소 마법의 수이거나, 그러한 수가 없으면 $-1$이다.

$i$가 1부터 $q$까지일 때 $b_i$는 처음 $i$번 바꾼 뒤 배열의 가능한 최소 마법의 수이거나, 그러한 수가 없으면 $-1$이다.

배타적 논리합은 $\oplus$ 기호로 표기하는 논리 연산이며, 다음 진리표로 정의된다:

음이 아닌 정수 $x$와 $y$의 비트별 배타적 논리합을 정의하자. $x$와 $y$를 각각 이진법으로 쓰되, 필요하면 더 짧은 수의 앞에 0을 채워 길이를 같게 맞춘다. 두 정수 $x$와 $y$의 비트별 배타적 논리합은 $x \oplus y$로도 표기하며, 이진법 표현의 각 자리가 $x$와 $y$의 해당 자리의 배타적 논리합인 음이 아닌 정수이다. 예를 들어 $5 \oplus 22 = 101_2 \oplus 10110_2 = 10011_2 = 19$이다.

올림피아드에서 제시된 프로그래밍 언어 중 파스칼에서는 배타적 논리합을 나타내는 데 <<xor>> 연산자를 쓰고, 나머지 프로그래밍 언어에서는 <<^>> 연산자를 쓴다.