Um conhecido programador está a experimentar o papel de ilusionista. O seu truque de assinatura consiste no seguinte.
Para um vetor dado de $n$ inteiros não negativos $a_1,a_2,\ldots,a_n$, ele escolhe rapidamente um número mágico $b$. Um inteiro não negativo $b$ é chamado mágico para o vetor se aplicar a operação OU exclusivo bit a bit com esse número a cada elemento transformar o vetor num vetor ordenado. Por outras palavras,
$$ (a_1\oplus b)\le(a_2\oplus b)\le\cdots\le(a_n\oplus b), $$
onde $\oplus$ é a operação OU exclusivo bit a bit.
Para tornar o truque mais impressionante, depois de apresentar um número mágico para o vetor dado, o ilusionista realiza a seguinte ação $q$ vezes. Convida os espectadores a alterar um dos elementos do vetor e, em seguida, tenta novamente apresentar um número mágico. O programador aperfeiçoou tanto a sua técnica de ilusionista que apresenta sempre aos espectadores o menor número mágico possível. Por vezes, o truque falha porque não é possível escolher um número mágico para o vetor obtido.
É necessário escrever um programa que, para o vetor inicialmente dado e também após cada alteração de um elemento, calcule o menor número mágico para o vetor obtido ou determine que tal número não existe.
Observação
O OU exclusivo é uma operação lógica, representada pelo símbolo $\oplus$, definida pela seguinte tabela de verdade:
| $x$ | $y$ | $x\oplus y$ |
|---|---|---|
| $0$ | $0$ | $0$ |
| $0$ | $1$ | $1$ |
| $1$ | $0$ | $1$ |
| $1$ | $1$ | $0$ |
Definamos o OU exclusivo bit a bit para dois inteiros não negativos $x$ e $y$. Escrevemos ambos os inteiros $x$ e $y$ em binário, acrescentando, se necessário, zeros à esquerda do mais curto para que tenham o mesmo comprimento. O OU exclusivo bit a bit de dois inteiros $x$ e $y$, também representado por $x\oplus y$, é o inteiro não negativo cujos dígitos binários são o OU exclusivo dos dígitos correspondentes de $x$ e $y$. Por exemplo, $5\oplus22=101_2\oplus10110_2=10011_2=19$.
Entre as linguagens de programação disponíveis na olimpíada, em Pascal utiliza-se o operador xor para representar o OU exclusivo; nas restantes linguagens de programação utiliza-se o operador ^.
Entrada
A primeira linha da entrada contém um inteiro $n$, a quantidade de números no vetor ($1\le n\le10^6$).
A segunda linha contém $n$ inteiros $a_1,a_2,\ldots,a_n$, os elementos do vetor ($0\le a_i<2^{30}$).
A terceira linha contém um inteiro $q$, a quantidade de alterações de elementos do vetor ($0\le q\le10^6$).
Cada uma das próximas $q$ linhas contém dois inteiros $p_i$ e $v_i$, em que $p_i$ é o índice do elemento do vetor que deve ser substituído ($1\le p_i\le n$), e $v_i$ é o novo valor desse elemento ($0\le v_i<2^{30}$).
Saída
A saída deve conter $(q+1)$ inteiros $b_0,b_1,\ldots,b_q$, um por linha.
O valor de $b_0$ deve ser o menor número mágico possível para o vetor inicial, ou $-1$ se tal número não existir.
Para $i$ de $1$ a $q$, o valor de $b_i$ deve ser o menor número mágico possível para o vetor após as primeiras $i$ alterações, ou $-1$ se tal número não existir.
Exemplos
Entrada 1
3 0 1 4 3 2 7 3 3 1 4
Saída 1
0 2 -1 4
Pontuação
| Subtarefa | Pontos | Restrições: $n$ | Restrições: $q$ | Restrições: $a_i,v_i$ | Subtarefas necessárias | Resultados durante a prova |
|---|---|---|---|---|---|---|
| $1$ | $30$ | $1\le n\le500$ | $0\le q\le500$ | $0\le a_i,v_i<2^9$ | Por teste | |
| $2$ | $29$ | $1\le n\le1000$ | $0\le q\le1000$ | $0\le a_i,v_i<2^{30}$ | $1$ | Por teste |
| $3$ | $21$ | $1\le n\le10^5$ | $0\le q\le10^5$ | $0\le a_i,v_i<2^{30}$ | $1,2$ | Pontos |
| $4$ | $20$ | $1\le n\le10^6$ | $0\le q\le10^6$ | $0\le a_i,v_i<2^{30}$ | $1$–$3$ | Pontos |