Un famoso programmatore si cimenta nel ruolo di illusionista. Il suo numero di punta consiste in quanto segue.
Per un dato array di $n$ interi non negativi $a_1,a_2,\ldots,a_n$, trova rapidamente un numero magico $b$. Un intero non negativo $b$ è detto magico per l'array se applicare l'operazione XOR bit a bit con questo numero a ogni elemento dell'array lo trasforma in un array ordinato. In altre parole,
$$(a_1\oplus b)\le(a_2\oplus b)\le\ldots\le(a_n\oplus b),$$
dove $\oplus$ è l'operazione XOR bit a bit.
Per rendere il numero più spettacolare, dopo aver mostrato il numero magico per l'array dato, l'illusionista esegue $q$ volte la seguente azione. Invita gli spettatori a modificare uno degli elementi dell'array e poi tenta nuovamente di mostrare un numero magico. Il programmatore ha perfezionato a tal punto la propria abilità di illusionista che ogni volta mostra agli spettatori il minimo numero magico possibile. Talvolta il numero non riesce, perché per l'array ottenuto non è possibile trovare un numero magico.
Scrivere un programma che, per l'array iniziale e dopo ogni modifica di un elemento, calcoli il minimo numero magico per l'array ottenuto oppure determini che un tale numero non esiste.
Nota
Lo XOR è un'operazione logica, indicata con il simbolo $\oplus$, definita dalla seguente tabella di verità:
| $x$ | $y$ | $x\oplus y$ |
|---|---|---|
| $0$ | $0$ | $0$ |
| $0$ | $1$ | $1$ |
| $1$ | $0$ | $1$ |
| $1$ | $1$ | $0$ |
Definiamo lo XOR bit a bit di due interi non negativi $x$ e $y$. Scriviamo ciascuno dei due interi $x$ e $y$ in base due, aggiungendo, se necessario, zeri iniziali al numero più corto per rendere uguali le lunghezze. Lo XOR bit a bit di due interi $x$ e $y$, indicato anch'esso con $x\oplus y$, è l'intero non negativo la cui rappresentazione binaria ha in ogni posizione lo XOR dei bit corrispondenti di $x$ e $y$. Ad esempio, $5\oplus22=101_2\oplus10110_2=10011_2=19$.
Tra i linguaggi di programmazione disponibili nella gara, Pascal usa l'operatore xor per indicare lo XOR, mentre gli altri linguaggi usano l'operatore ^.
Input
La prima riga dell'input contiene un intero $n$, il numero di elementi dell'array ($1\le n\le10^6$).
La seconda riga contiene $n$ interi $a_1,a_2,\ldots,a_n$, gli elementi dell'array ($0\le a_i<2^{30}$).
La terza riga contiene un intero $q$, il numero di modifiche a un elemento dell'array ($0\le q\le10^6$).
Le successive $q$ righe contengono ciascuna due interi $p_i$ e $v_i$, dove $p_i$ è l'indice dell'elemento dell'array da sostituire ($1\le p_i\le n$) e $v_i$ è il nuovo valore di tale elemento ($0\le v_i<2^{30}$).
Output
L'output deve contenere $q+1$ interi $b_0,b_1,\ldots,b_q$, uno per riga.
Il valore $b_0$ è il minimo numero magico possibile per l'array iniziale, oppure $-1$ se un tale numero non esiste.
Per $i$ da $1$ a $q$, il valore $b_i$ è il minimo numero magico possibile per l'array dopo le prime $i$ modifiche, oppure $-1$ se un tale numero non esiste.
Esempi
Input 1
3 0 1 4 3 2 7 3 3 1 4
Output 1
0 2 -1 4
Valutazione
| Sottoproblema | Punti | Vincoli: $n$ | Vincoli: $q$ | Vincoli: $a_i,v_i$ | Sottoproblemi richiesti | Risultati durante la gara |
|---|---|---|---|---|---|---|
| $1$ | $30$ | $1\le n\le500$ | $0\le q\le500$ | $0\le a_i,v_i<2^9$ | Per singolo test | |
| $2$ | $29$ | $1\le n\le1000$ | $0\le q\le1000$ | $0\le a_i,v_i<2^{30}$ | $1$ | Per singolo test |
| $3$ | $21$ | $1\le n\le10^5$ | $0\le q\le10^5$ | $0\le a_i,v_i<2^{30}$ | $1,2$ | Punteggio |
| $4$ | $20$ | $1\le n\le10^6$ | $0\le q\le10^6$ | $0\le a_i,v_i<2^{30}$ | $1$–$3$ | Punteggio |