Сорбет и Джелато узнали важные данные. Эти данные являются тайной, которую нельзя разглашать, но и их объем был настолько большим, что полностью запомнить их не представлялось возможным. Поэтому они решили их зашифровать.
Сорбет составил из данных сообщение. После оцифровки сообщение представляло из себя последовательность M из n целых неотрицательных чисел. Для шифрования Сорбет сгенерировал случайный ключ K, который также являлся последовательностью из n целых неотрицательных чисел.
После этого он вычислил зашифрованное сообщение A как побитовое исключающее ИЛИ каждого соответствующего элемента исходного сообщения и ключа (A
i = M
i ⊕ K
i).
Зашифрованное сообщение Сорбет оставил себе, а для обеспечения безопасности ключ отправил Джелато, а сам его стер. Однако канал передачи оказался ненадежным и Джелато получил ключ P, в котором некоторые элементы из K поменялись местами. То есть получил некоторую перестановку исходного ключа K.
Когда настало время обратно раскодировать сообщение, они с ужасом осознали проблему. Однако Сорбет помнил, что исходное сообщение было довольно маленьким лексикографически (но содержало только неотрицательные числа).
Поэтому Сорбет и Джелато решили узнать, каково лексикографически минимальное сообщение, которое могло быть зашифровано. Помогите им это определить.
Входные данные:
Первая строка содержит одно целое число n (1 ≤ n ≤ 300000) — длину сообщения.
Вторая строка содержит n целых чисел A
1, A
2, ..., A
n (0 ≤ Ai < 2
30) — зашифрованное сообщение.
Третья строка содержит n целых чисел P
1, P
2, ..., P
n (0 ≤ Pi < 2
30) — ключ шифрования, элементы которого переставлены произвольным образом.
Выходные данные:
Выведите одну строку с n целыми числами — лексикографически минимально возможное исходное сообщение. Напомним, что все числа в нем должны быть неотрицательны.
Примеры:
| Входные данные |
Выходные данные |
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 |
Пояснение:
В первом примере решением является (10, 3, 28), потому что 8 ⊕ 2 = 10, 4 ⊕ 7 = 3 и 13 ⊕ 17 = 28.
Другие возможные перестановки ключа дают сообщения (25, 6, 10), (25, 3, 15), (10, 21, 10), (15, 21, 15) и (15, 6, 28), все из которых лексикографически больше, чем оптимальное решение.