Un conocido programador prueba suerte como ilusionista. Su truco estrella consiste en lo siguiente.
Para un arreglo dado de $n$ enteros no negativos $a_1,a_2,\ldots,a_n$, encuentra rápidamente un número mágico $b$. Un entero no negativo $b$ se llama mágico para el arreglo si aplicar la operación O exclusivo bit a bit con este número a cada elemento del arreglo lo convierte en un arreglo ordenado. En otras palabras,
$$(a_1\oplus b)\le(a_2\oplus b)\le\ldots\le(a_n\oplus b),$$
donde $\oplus$ es la operación O exclusivo bit a bit.
Para que el truco resulte más espectacular, después de presentar un número mágico para el arreglo dado, el ilusionista realiza $q$ veces la siguiente acción. Propone a los espectadores modificar un elemento del arreglo y luego intenta presentar de nuevo un número mágico. El programador ha perfeccionado tanto su habilidad como ilusionista que cada vez presenta a los espectadores el menor número mágico posible. A veces el truco falla, ya que es imposible encontrar un número mágico para el arreglo obtenido.
Debes escribir un programa que, para el arreglo inicial dado y después de cada modificación de un elemento, calcule el menor número mágico para el arreglo obtenido o determine que no existe tal número.
Nota
El O exclusivo es una operación lógica, denotada por $\oplus$, que se define mediante la siguiente tabla de verdad:
| $x$ | $y$ | $x\oplus y$ |
|---|---|---|
| $0$ | $0$ | $0$ |
| $0$ | $1$ | $1$ |
| $1$ | $0$ | $1$ |
| $1$ | $1$ | $0$ |
Definamos el O exclusivo bit a bit de dos enteros no negativos $x$ e $y$. Escribimos cada entero $x$ e $y$ en sistema binario, añadiendo, si es necesario, ceros iniciales al más corto hasta que ambos tengan la misma longitud. El O exclusivo bit a bit de dos enteros $x$ e $y$, también denotado por $x\oplus y$, es el entero no negativo cuyo dígito en cada posición de su representación binaria es el O exclusivo de los dígitos correspondientes de $x$ e $y$. Por ejemplo, $5\oplus22=101_2\oplus10110_2=10011_2=19$.
Entre los lenguajes de programación disponibles en la olimpiada, Pascal utiliza el operador xor para denotar el O exclusivo; los demás lenguajes de programación utilizan el operador ^.
Entrada
La primera línea contiene un entero $n$, la cantidad de números del arreglo ($1\le n\le10^6$).
La segunda línea contiene $n$ enteros $a_1,a_2,\ldots,a_n$, los elementos del arreglo ($0\le a_i<2^{30}$).
La tercera línea contiene un entero $q$, la cantidad de modificaciones de un elemento del arreglo ($0\le q\le10^6$).
Las siguientes $q$ líneas contienen dos enteros $p_i$ y $v_i$ cada una, donde $p_i$ es el índice del elemento del arreglo que se debe reemplazar ($1\le p_i\le n$), y $v_i$ es el nuevo valor de ese elemento ($0\le v_i<2^{30}$).
Salida
La salida debe contener $(q+1)$ enteros $b_0,b_1,\ldots,b_q$, uno por línea.
El valor $b_0$ es el menor número mágico posible para el arreglo inicial, o $-1$ si tal número no existe.
Para $i$ de $1$ a $q$, el valor $b_i$ es el menor número mágico posible para el arreglo después de las primeras $i$ modificaciones, o $-1$ si tal número no existe.
Ejemplos
Entrada 1
3 0 1 4 3 2 7 3 3 1 4
Salida 1
0 2 -1 4
Subtareas
| Subtarea | Puntos | Restricciones: $n$ | Restricciones: $q$ | Restricciones: $a_i,v_i$ | Subtareas necesarias | Resultados durante la competición |
|---|---|---|---|---|---|---|
| 1 | 30 | $1\le n\le500$ | $0\le q\le500$ | $0\le a_i,v_i<2^9$ | Por caso de prueba | |
| 2 | 29 | $1\le n\le1000$ | $0\le q\le1000$ | $0\le a_i,v_i<2^{30}$ | 1 | Por caso de prueba |
| 3 | 21 | $1\le n\le10^5$ | $0\le q\le10^5$ | $0\le a_i,v_i<2^{30}$ | 1, 2 | Puntos |
| 4 | 20 | $1\le n\le10^6$ | $0\le q\le10^6$ | $0\le a_i,v_i<2^{30}$ | 1–3 | Puntos |