Un célèbre programmeur s'essaie au rôle d'illusionniste. Son tour de prédilection est le suivant.
Pour un tableau donné de $n$ entiers non négatifs $a_1,a_2,\ldots,a_n$, il trouve rapidement un nombre magique $b$. Un entier non négatif $b$ est dit magique pour le tableau si l'application de l'opération OU exclusif bit à bit avec ce nombre à chaque élément du tableau transforme celui-ci en un tableau trié. Autrement dit,
$$ (a_1\oplus b)\le(a_2\oplus b)\le\ldots\le(a_n\oplus b), $$
où $\oplus$ est l'opération OU exclusif bit à bit.
Pour rendre son tour plus spectaculaire, après avoir présenté un nombre magique pour le tableau donné, l'illusionniste effectue $q$ fois l'action suivante. Il propose aux spectateurs de modifier un élément du tableau, puis tente de nouveau de présenter un nombre magique. Le programmeur a tellement perfectionné son art d'illusionniste qu'il présente à chaque fois aux spectateurs le plus petit nombre magique possible. Parfois, le tour échoue, car il est impossible de trouver un nombre magique pour le tableau obtenu.
Vous devez écrire un programme qui, pour le tableau initial donné ainsi qu'après chaque modification d'un élément, calcule le plus petit nombre magique pour le tableau obtenu, ou détermine qu'un tel nombre n'existe pas.
Remarque
Le OU exclusif est une opération logique, notée $\oplus$, définie par la table de vérité suivante :
| $x$ | $y$ | $x\oplus y$ |
|---|---|---|
| $0$ | $0$ | $0$ |
| $0$ | $1$ | $1$ |
| $1$ | $0$ | $1$ |
| $1$ | $1$ | $0$ |
Définissons le OU exclusif bit à bit de deux entiers non négatifs $x$ et $y$. Écrivons chacun des entiers $x$ et $y$ en base deux, en complétant si nécessaire le plus court par des zéros initiaux pour qu'ils aient la même longueur. Le OU exclusif bit à bit de deux entiers $x$ et $y$, également noté $x\oplus y$, est l'entier non négatif dont chaque chiffre en base deux est le OU exclusif des chiffres correspondants de $x$ et $y$. Par exemple, $5\oplus22=101_2\oplus10110_2=10011_2=19$.
Parmi les langages de programmation proposés à l'olympiade, le langage Pascal utilise l'opérateur xor pour le OU exclusif ; les autres langages de programmation utilisent l'opérateur ^.
Entrée
La première ligne de l'entrée contient un entier $n$, le nombre d'éléments du tableau ($1\le n\le10^6$).
La deuxième ligne contient $n$ entiers $a_1,a_2,\ldots,a_n$, les éléments du tableau ($0\le a_i<2^{30}$).
La troisième ligne contient un entier $q$, le nombre de modifications d'un élément du tableau ($0\le q\le10^6$).
Les $q$ lignes suivantes contiennent chacune deux entiers $p_i$ et $v_i$, où $p_i$ est l'indice de l'élément du tableau à remplacer ($1\le p_i\le n$), et $v_i$ est la nouvelle valeur de cet élément ($0\le v_i<2^{30}$).
Sortie
La sortie doit contenir $q+1$ entiers $b_0,b_1,\ldots,b_q$, un par ligne.
La valeur $b_0$ est soit le plus petit nombre magique possible pour le tableau initial, soit $-1$ si un tel nombre n'existe pas.
Pour $i$ allant de $1$ à $q$, la valeur $b_i$ est soit le plus petit nombre magique possible pour le tableau après les $i$ premières modifications, soit $-1$ si un tel nombre n'existe pas.
Exemples
Entrée 1
3 0 1 4 3 2 7 3 3 1 4
Sortie 1
0 2 -1 4
Sous-tâches
| Sous-tâche | Points | Contraintes sur $n$ | Contraintes sur $q$ | Contraintes sur $a_i,v_i$ | Sous-tâches requises | Résultats pendant l'épreuve |
|---|---|---|---|---|---|---|
| $1$ | $30$ | $1\le n\le500$ | $0\le q\le500$ | $0\le a_i,v_i<2^9$ | Test par test | |
| $2$ | $29$ | $1\le n\le1000$ | $0\le q\le1000$ | $0\le a_i,v_i<2^{30}$ | $1$ | Test par test |
| $3$ | $21$ | $1\le n\le10^5$ | $0\le q\le10^5$ | $0\le a_i,v_i<2^{30}$ | $1,2$ | Points |
| $4$ | $20$ | $1\le n\le10^6$ | $0\le q\le10^6$ | $0\le a_i,v_i<2^{30}$ | $1$–$3$ | Points |