Модуль: Жадные алгоритмы


Задача

9 /9


Сорбет и Джелато зашифровали сообщение

Задача

Сорбет и Джелато узнали важные данные. Эти данные являются тайной, которую нельзя разглашать, но и их объем был настолько большим, что полностью запомнить их не представлялось возможным. Поэтому они решили их зашифровать.

Сорбет составил из данных сообщение. После оцифровки сообщение представляло из себя последовательность M из n целых неотрицательных чисел. Для шифрования Сорбет сгенерировал случайный ключ K, который также являлся последовательностью из n целых неотрицательных чисел.
После этого он вычислил зашифрованное сообщение A как побитовое исключающее ИЛИ каждого соответствующего элемента исходного сообщения и ключа (Ai = Mi ⊕ Ki).
Зашифрованное сообщение Сорбет оставил себе, а для обеспечения безопасности ключ отправил Джелато, а сам его стер. Однако канал передачи оказался ненадежным и Джелато получил ключ P, в котором некоторые элементы из K поменялись местами. То есть получил некоторую перестановку исходного ключа K.

Когда настало время обратно раскодировать сообщение, они с ужасом осознали проблему. Однако Сорбет помнил, что исходное сообщение было довольно маленьким лексикографически (но содержало только неотрицательные числа).
Поэтому Сорбет и Джелато решили узнать, каково лексикографически минимальное сообщение, которое могло быть зашифровано. Помогите им это определить.

Входные данные:
Первая строка содержит одно целое число n (1 ≤ n ≤ 300000) — длину сообщения.
Вторая строка содержит n целых чисел A1, A2, ..., An (0 ≤ Ai < 230) — зашифрованное сообщение.
Третья строка содержит n целых чисел P1, P2, ..., Pn (0 ≤ Pi < 230) — ключ шифрования, элементы которого переставлены произвольным образом.

Выходные данные:
Выведите одну строку с 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), все из которых лексикографически больше, чем оптимальное решение.