Ein bekannter Programmierer versucht sich als Illusionist. Sein berühmtester Trick funktioniert wie folgt.

Für ein gegebenes Array aus $n$ nichtnegativen ganzen Zahlen $a_1, a_2, \ldots, a_n$ findet er schnell eine magische Zahl $b$. Eine nichtnegative ganze Zahl $b$ heißt magisch für das Array, wenn die bitweise Exklusiv-ODER-Verknüpfung jedes Arrayelements mit dieser Zahl das Array in ein sortiertes Array verwandelt. Mit anderen Worten gilt

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

wobei $\oplus$ die bitweise Exklusiv-ODER-Verknüpfung bezeichnet.

Um den Trick eindrucksvoller zu machen, führt der Illusionist nach dem Vorzeigen der magischen Zahl für das gegebene Array $q$-mal folgende Aktion aus. Er fordert die Zuschauer auf, eines der Arrayelemente zu ändern, und versucht danach erneut, eine magische Zahl vorzuzeigen. Dabei hat der Programmierer seine Fähigkeiten als Illusionist so weit perfektioniert, dass er den Zuschauern jedes Mal die kleinstmögliche magische Zahl zeigt. Manchmal misslingt der Trick, weil für das entstandene Array keine magische Zahl gefunden werden kann.

Schreiben Sie ein Programm, das für das anfänglich gegebene Array sowie nach jeder Änderung eines Elements die kleinste magische Zahl für das entstandene Array berechnet oder feststellt, dass es keine solche Zahl gibt.

Hinweis

Exklusiv-ODER ist eine logische Operation, die mit dem Zeichen $\oplus$ bezeichnet wird und durch die folgende Wahrheitstabelle definiert ist:

Definieren wir das bitweise Exklusiv-ODER für zwei nichtnegative ganze Zahlen $x$ und $y$. Wir schreiben jede der ganzen Zahlen $x$ und $y$ im Binärsystem und ergänzen gegebenenfalls die kürzere Darstellung mit führenden Nullen, bis beide gleich lang sind. Das bitweise Exklusiv-ODER zweier ganzer Zahlen $x$ und $y$, ebenfalls mit $x \oplus y$ bezeichnet, ist eine nichtnegative ganze Zahl, deren jede Binärziffer das Exklusiv-ODER der entsprechenden Ziffern der Zahlen $x$ und $y$ ist. Beispielsweise ist $5 \oplus 22 = 101_2 \oplus 10110_2 = 10011_2 = 19$.

Unter den bei der Olympiade angebotenen Programmiersprachen wird in Pascal der Operator xor für Exklusiv-ODER verwendet, in den übrigen Programmiersprachen der Operator ^.

Eingabe

Die erste Eingabezeile enthält eine ganze Zahl $n$, die Anzahl der Zahlen im Array ($1 \le n \le 10^6$).

Die zweite Zeile enthält $n$ ganze Zahlen $a_1, a_2, \ldots, a_n$, die Elemente des Arrays ($0 \le a_i < 2^{30}$).

Die dritte Zeile enthält eine ganze Zahl $q$, die Anzahl der Änderungen eines Arrayelements ($0 \le q \le 10^6$).

Die folgenden $q$ Zeilen enthalten jeweils zwei ganze Zahlen $p_i$ und $v_i$. Dabei ist $p_i$ der Index des zu ersetzenden Arrayelements ($1 \le p_i \le n$), und $v_i$ ist der neue Wert dieses Elements ($0 \le v_i < 2^{30}$).

Ausgabe

Die Ausgabe muss $(q + 1)$ ganze Zahlen $b_0, b_1, \ldots, b_q$ enthalten, jeweils eine pro Zeile.

Der Wert $b_0$ ist entweder die kleinstmögliche magische Zahl für das ursprüngliche Array oder $-1$, wenn es keine solche Zahl gibt.

Für $i$ von $1$ bis $q$ ist der Wert $b_i$ entweder die kleinstmögliche magische Zahl für das Array nach den ersten $i$ Änderungen oder $-1$, wenn es keine solche Zahl gibt.

Beispiele

Eingabe 1

3
0 1 4
3
2 7
3 3
1 4

Ausgabe 1

0
2
-1
4

Teilaufgaben