Problem
Sorbet and Gelato learned important data. This data is a secret that cannot be disclosed, but their volume was so large that it was not possible to remember them completely. So they decided to encrypt them.
Sorbet compiled a message from the data. After digitization, the message was a sequence M of n non-negative integers. For encryption, Sorbet generated a random key K, which was also a sequence of n non-negative integers.
After that, it computed the encrypted message A as a bitwise XOR of each corresponding element of the original message and the key (A
i = M
i ⊕ K
i) .
Sorbet kept the encrypted message for himself, and to ensure security, the key was sent to Gelato, and he erased it. However, the transmission channel turned out to be unreliable and Gelato received the key P, in which some elements from K were swapped. That is, I got some permutation of the original key K.
When it was time to decode the message back, they were horrified to realize the problem. However, Sorbet remembered that the original message was quite small lexicographically (but contained only non-negative numbers).
So Sorbet and Gelato decided to find out what is the lexicographically smallest message that could be encrypted. Help them figure it out.
Input:
The first line contains a single integer n (1 ≤ n ≤ 300000) — message length.
The second line contains n integers A
1, A
2, ..., A
n (0 ≤ Ai < 2
30) — encrypted message.
The third line contains n integers P
1, P
2, ..., P
n (0 ≤ Pi < 2
30) — an encryption key whose elements are rearranged arbitrarily.
Output:
Print one line with n integers — the lexicographically smallest possible original message. Recall that all numbers in it must be non-negative.
Examples:
| Input |
Output |
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 |
Explanation:
In the first example, the solution is (10, 3, 28) because 8 ⊕ 2 = 10, 4 ⊕ 7 = 3 and 13 ⊕ 17 = 28.
Other possible key permutations give the messages (25, 6, 10), (25, 3, 15), (10, 21, 10), (15, 21, ;15) and (15, 6, 28), all of which are lexicographically larger than the optimal solution.