Multiset e XORs
Problem
Você tem q consultas e um multiconjunto A que inicialmente contém apenas o número 0. Existem três tipos de consultas:
- +x — adicione o número x ao multiconjunto A.
- -x — remova uma ocorrência do número x do multiconjunto A. É garantido que pelo menos um número x esteja presente no multiconjunto neste momento.
- ? x — você recebe um número x, precisa calcular o OR exclusivo bit a bit máximo (também conhecido como XOR) do número x e algum número y do multiconjunto A.
Conjunto múltiplo — este é um conjunto que permite vários elementos idênticos.
Entrada:
A primeira linha da entrada contém o número q (1 ≤ q ≤ 200000) — o número de solicitações que Vasiliy precisa processar.
Cada uma das seguintes q linhas da entrada contém um dos três caracteres "+", "-" ou "?" e o número x
i (1 ≤ x
i ≤ 10
9). É garantido que haja pelo menos uma consulta "?" na entrada.
Observe que o número 0 sempre estará presente no multiconjunto.
Saída:
Para cada solicitação como "?" imprimir um único inteiro — o valor máximo do XOR bit a bit para o número x
i e qualquer número do multiconjunto A.
Exemplo:
| Entrada |
Saída |
10
+8
+9
+11
+ 6
+ 1
? 3
- 8
? 3
? 8
? 11 |
11
10
14
13 |