Znany programista próbuje swoich sił jako iluzjonista. Jego popisowa sztuczka polega na następującym.

Dla danej tablicy $n$ nieujemnych liczb całkowitych $a_1, a_2, \ldots, a_n$ szybko dobiera on magiczną liczbę $b$. Nieujemna liczba całkowita $b$ jest nazywana magiczną dla tablicy, jeżeli zastosowanie operacji bitowej alternatywy wykluczającej z tą liczbą do każdego elementu tablicy zamienia ją w tablicę posortowaną. Innymi słowy,

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

gdzie $\oplus$ oznacza operację bitowej alternatywy wykluczającej.

Aby sztuczka była bardziej efektowna, po przedstawieniu magicznej liczby dla danej tablicy iluzjonista $q$ razy wykonuje następującą czynność. Proponuje widzom zmianę jednego elementu tablicy, po czym ponownie próbuje przedstawić magiczną liczbę. Programista doprowadził przy tym swoje umiejętności iluzjonisty do takiej perfekcji, że za każdym razem przedstawia widzom najmniejszą możliwą magiczną liczbę. Czasem sztuczka się nie udaje, ponieważ dla otrzymanej tablicy nie można dobrać magicznej liczby.

Napisz program, który dla danej początkowej tablicy, a także po każdej zmianie elementu, oblicza najmniejszą magiczną liczbę dla otrzymanej tablicy albo stwierdza, że taka liczba nie istnieje.

Uwagi

Alternatywa wykluczająca to operacja logiczna oznaczana symbolem $\oplus$, określona następującą tabelą prawdy:

Zdefiniujmy bitową alternatywę wykluczającą dla dwóch nieujemnych liczb całkowitych $x$ i $y$. Zapiszmy każdą z liczb całkowitych $x$ i $y$ w systemie dwójkowym, w razie potrzeby uzupełniając krótszy zapis zerami wiodącymi, aby oba zapisy miały tę samą długość. Bitowa alternatywa wykluczająca dwóch liczb całkowitych $x$ i $y$, oznaczana również jako $x \oplus y$, jest nieujemną liczbą całkowitą, której każdy bit w zapisie dwójkowym jest alternatywą wykluczającą odpowiednich bitów liczb $x$ i $y$. Na przykład $5 \oplus 22 = 101_2 \oplus 10110_2 = 10011_2 = 19$.

Spośród języków programowania dostępnych na olimpiadzie w języku Pascal do oznaczania alternatywy wykluczającej używa się operatora xor, a w pozostałych językach programowania operatora ^.

Wejście

Pierwszy wiersz danych wejściowych zawiera liczbę całkowitą $n$ — liczbę liczb w tablicy ($1 \le n \le 10^6$).

Drugi wiersz zawiera $n$ liczb całkowitych $a_1, a_2, \ldots, a_n$ — elementy tablicy ($0 \le a_i < 2^{30}$).

Trzeci wiersz zawiera liczbę całkowitą $q$ — liczbę zmian elementu tablicy ($0 \le q \le 10^6$).

Każdy z następnych $q$ wierszy zawiera dwie liczby całkowite $p_i$ i $v_i$, gdzie $p_i$ jest numerem elementu tablicy, który należy zastąpić ($1 \le p_i \le n$), a $v_i$ jest nową wartością tego elementu ($0 \le v_i < 2^{30}$).

Wyjście

Dane wyjściowe powinny zawierać $(q + 1)$ liczb całkowitych $b_0, b_1, \ldots, b_q$, po jednej w wierszu.

Wartość $b_0$ jest najmniejszą możliwą magiczną liczbą dla początkowej tablicy albo wynosi $-1$, jeżeli taka liczba nie istnieje.

Dla $i$ od $1$ do $q$ wartość $b_i$ jest najmniejszą możliwą magiczną liczbą dla tablicy po pierwszych $i$ zmianach albo wynosi $-1$, jeżeli taka liczba nie istnieje.

Przykład

Wejście 1

3
0 1 4
3
2 7
3 3
1 4

Wyjście 1

0
2
-1
4

Podzadania