Xorcisten

Xorcisten Roxanne은 리스트를 아주 빠르게 정렬하는 특별한 능력이 있다. 정수 리스트 $a_1, a_2, \dots, a_N$을 보면 그녀는 곧바로 다음 식이 성립하는 정수 $X$를 찾는다.

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

여기서 $\oplus$는 비트 XOR이다. 두 수를 2진법으로 쓰고, 가장 낮은 자리부터 차례로 두 자리가 같으면 0, 다르면 1을 쓴다. 자리올림 없이 2진수 덧셈을 하는 것과 같다.

그녀가 할 일은 각 $a_i$를 $a_i \oplus x$로 바꾸는 것뿐이고, 그러면 리스트가 정렬된다.

여러 회사가 아주 긴 리스트를 정렬해 달라고 Roxanne을 자주 고용한다. 그런데 어느 날 그녀는 자신의 능력이 사라졌다는 것을 알게 된다. 당신의 과제는 그녀가 계속 일할 수 있도록 프로그램을 작성하는 것이다.

비음수 정수 $a_1, \dots, a_N$과 $Q$개의 변경 $p_i, v_i$가 주어진다. 이는 $a_{p_i}$가 $v_i$로 바뀐다는 뜻이다. $c_i$는 처음 $i$개의 변경을 적용한 뒤, 리스트 $a_1 \oplus X, \dots, a_N \oplus X$가 정렬되도록 하는 가장 작은 비음수 정수 $X$이다. $c_0, c_1, \dots, c_Q$를 출력한다. 그런 $X$가 없으면 $-1$을 출력한다.

첫 줄에 정수 $N$ ($1 \leq N \leq 10^6$)이 주어진다. 리스트에 있는 수의 개수이다.

둘째 줄에는 $N$개의 정수 $a_1, a_2, \dots, a_N$ ($0 \leq a_i < 2^{30}$)이 주어진다.

셋째 줄에는 변경 횟수 $Q$ ($0 \leq Q \leq 10^6$)가 주어진다.

이어지는 $Q$개의 줄에는 정수 두 개 $p_i$ ($1 \leq p_i \leq N$)와 $v_i$ ($0 \leq v_i < 2^{30}$)가 주어진다. 이는 $a_{p_i}$를 $v_i$로 바꾼다는 뜻이다.

$Q+1$개의 줄을 출력한다. $i$번째 줄(0부터 센다)에는 변경 $1, 2, \dots, i$를 적용한 뒤 리스트를 정렬하는 가장 작은 $x$인 $c_i$를 출력한다. 그런 $x$가 없으면 $-1$을 출력한다.

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