Problem
Sorbet e Gelato aprenderam dados importantes. Esses dados são um segredo que não pode ser divulgado, mas seu volume era tão grande que não era possível lembrá-los completamente. Então eles decidiram criptografá-los.
Sorbet compilou uma mensagem a partir dos dados. Após a digitalização, a mensagem era uma sequência M de n inteiros não negativos. Para criptografia, Sorbet gerou uma chave aleatória K, que também era uma sequência de n inteiros não negativos.
Depois disso, ele calculou a mensagem criptografada A como um XOR bit a bit de cada elemento correspondente da mensagem original e a chave (A
i = M
i ⊕ K
i) .
Sorbet guardou a mensagem criptografada para si mesmo e, para garantir a segurança, a chave foi enviada para Gelato e ele a apagou. No entanto, o canal de transmissão não era confiável e Gelato recebeu a chave P, na qual alguns elementos de K foram trocados. Ou seja, obtive alguma permutação da chave original K.
Quando chegou a hora de decodificar a mensagem de volta, eles ficaram horrorizados ao perceber o problema. No entanto, Sorbet lembrou que a mensagem original era muito pequena lexicograficamente (mas continha apenas números não negativos).
Então Sorbet e Gelato decidiram descobrir qual é a menor mensagem lexicograficamente que poderia ser criptografada. Ajude-os a descobrir.
Entrada:
A primeira linha contém um único inteiro n (1 ≤ n ≤ 300000) — tamanho da mensagem.
A segunda linha contém n inteiros A
1, A
2, ..., A
n (0 ≤ Ai < 2
30) — mensagem criptografada.
A terceira linha contém n inteiros P
1, P
2, ..., P
n (0 ≤ Pi < 2
30) — uma chave de criptografia cujos elementos são rearranjados arbitrariamente.
Saída:
Imprima uma linha com n inteiros — a menor mensagem original lexicograficamente possível. Lembre-se de que todos os números nele devem ser não negativos.
Exemplos:
| Entrada |
Saída |
3
8 4 13
17 2 7
| 10 3 28 |
5
12 7 87 22 11
18 39 9 12 16
| 0 14 69 6 44 |
Explicação:
No primeiro exemplo, a solução é (10, 3, 28) porque 8 ⊕ 2 = 10, 4 ⊕ 7 = 3 e 13 ⊕ 17 = 28.
Outras permutações de chaves possíveis fornecem as mensagens (25, 6, 10), (25, 3, 15), (10, 21, 10), (15, 21, ;15) e (15, 6, 28), todos lexicograficamente maiores que a solução ótima.