Problem
Sorbet y Gelato aprendieron datos importantes. Estos datos son un secreto que no se puede revelar, pero su volumen era tan grande que no era posible recordarlos por completo. Así que decidieron encriptarlos.
Sorbet compiló un mensaje a partir de los datos. Después de la digitalización, el mensaje era una secuencia M de n enteros no negativos. Para el cifrado, Sorbet generó una clave aleatoria K, que también era una secuencia de n enteros no negativos.
Después de eso, calculó el mensaje cifrado A como un XOR bit a bit de cada elemento correspondiente del mensaje original y la clave (A
i = M
i ⊕ K
yo).
Sorbet se quedó con el mensaje encriptado y, para garantizar la seguridad, le envió la clave a Gelato y él la borró. Sin embargo, el canal de transmisión resultó ser poco fiable y Gelato recibió la clave P, en la que se intercambiaron algunos elementos de K. Es decir, obtuve alguna permutación de la clave original K.
Cuando llegó el momento de decodificar el mensaje, se horrorizaron al darse cuenta del problema. Sin embargo, Sorbet recordó que el mensaje original era bastante pequeño desde el punto de vista lexicográfico (pero solo contenía números no negativos).
Así que Sorbet y Gelato decidieron averiguar cuál es el mensaje lexicográficamente más pequeño que se puede cifrar. Ayúdalos a resolverlo.
Entrada:
La primera línea contiene un único número entero n (1 ≤ n ≤ 300000) — longitud del mensaje.
La segunda línea contiene n enteros A
1, A
2, ..., A
n (0 ≤ Ai < 2
30) — mensaje encriptado.
La tercera línea contiene n enteros P
1, P
2, ..., P
n (0 ≤ Pi < 2
30) — una clave de cifrado cuyos elementos se reorganizan arbitrariamente.
Salida:
Imprime una línea con n enteros — el mensaje original lexicográficamente más pequeño posible. Recuerde que todos los números que contiene deben ser no negativos.
Ejemplos:
| Entrada |
Salida |
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 |
Explicación:
En el primer ejemplo, la solución es (10, 3, 28) porque 8 ⊕ 2 = 10, 4 ⊕ 7 = 3 y 13 ⊕ 17 = 28.
Otras posibles permutaciones de teclas dan los mensajes (25, 6, 10), (25, 3, 15), (10, 21, 10), (15, 21, ;15) y (15, 6, 28), todas las cuales son lexicográficamente más grandes que la solución óptima.