유명한 프로그래머가 마술사 역할에 도전하고 있다. 그의 대표적인 마술은 다음과 같다.

음이 아닌 정수 $n$개로 이루어진 배열 $a_1,a_2,\ldots,a_n$이 주어지면, 그는 빠르게 마법의 수 $b$를 찾는다. 음이 아닌 정수 $b$를 배열의 각 원소와 비트 단위 배타적 논리합 연산하여 배열이 정렬되면, $b$를 그 배열의 마법의 수라고 한다. 즉,

$$ (a_1\oplus b)\le(a_2\oplus b)\le\ldots\le(a_n\oplus b), $$

여기서 $\oplus$는 비트 단위 배타적 논리합 연산이다.

마술을 더욱 인상적으로 만들기 위해, 마술사는 주어진 배열의 마법의 수를 보여 준 뒤 다음 동작을 $q$번 수행한다. 관객에게 배열의 원소 하나를 변경하도록 요청하고, 다시 마법의 수를 보여 주려고 한다. 이 프로그래머는 마술 실력을 매우 정교하게 갈고닦아서 매번 관객에게 가능한 마법의 수 중 최솟값을 보여 준다. 변경된 배열의 마법의 수를 찾을 수 없어 마술이 실패하는 경우도 있다.

주어진 초기 배열과 각 원소 변경 후의 배열에 대해 마법의 수의 최솟값을 계산하거나, 그러한 수가 없음을 판정하는 프로그램을 작성해야 한다.

참고

배타적 논리합은 $\oplus$로 나타내는 논리 연산이며, 다음 진리표로 정의된다.

음이 아닌 두 정수 $x$와 $y$의 비트 단위 배타적 논리합을 정의하자. 각 정수 $x$와 $y$를 이진법으로 표현하고, 필요한 경우 더 짧은 쪽의 앞에 $0$을 붙여 길이를 같게 한다. 두 정수 $x$와 $y$의 비트 단위 배타적 논리합도 $x\oplus y$로 나타내며, 그 이진 표현의 각 자리 숫자가 $x$와 $y$의 대응하는 자리 숫자들의 배타적 논리합인 음이 아닌 정수이다. 예를 들어, $5\oplus22=101_2\oplus10110_2=10011_2=19$이다.

올림피아드에서 제공되는 프로그래밍 언어 중 Pascal에서는 배타적 논리합을 나타내는 연산자로 xor를 사용하고, 다른 프로그래밍 언어에서는 ^를 사용한다.

입력

첫 번째 줄에는 배열의 수의 개수를 나타내는 정수 $n$이 주어진다 ($1\le n\le10^6$).

두 번째 줄에는 배열의 원소인 정수 $n$개 $a_1,a_2,\ldots,a_n$이 주어진다 ($0\le a_i<2^{30}$).

세 번째 줄에는 배열 원소를 변경하는 횟수인 정수 $q$가 주어진다 ($0\le q\le10^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$이다.

$1$부터 $q$까지의 $i$에 대해, $b_i$는 처음 $i$번 변경한 후의 배열의 가능한 마법의 수 중 최솟값이며, 그러한 수가 존재하지 않으면 $-1$이다.

예제

입력 1

3
0 1 4
3
2 7
3 3
1 4

출력 1

0
2
-1
4

서브태스크