Problem
Sorbet 和 Gelato 学到了重要的数据。这些数据是不能公开的秘密,但体积之大,根本不可能完全记住。所以他们决定加密它们。
Sorbet 从数据中编辑了一条信息。数字化后,消息是一个由 n 个非负整数组成的序列 M。为了加密,Sorbet 生成了一个随机密钥 K,它也是一个由 n 个非负整数组成的序列。
之后,它将加密消息 A 计算为原始消息的每个相应元素和密钥的按位异或 (A
i = M
i ⊕ K
我) .
Sorbet 为自己保留了加密信息,为了确保安全,密钥被发送给了 Gelato,他将其删除。然而,传输通道被证明是不可靠的,Gelato 收到了密钥 P,其中交换了来自 K 的一些元素。也就是说,我得到了原始密钥 K 的一些排列。
当需要解码回信息时,他们惊恐地意识到了这个问题。然而,Sorbet 记得原始消息在字典上非常小(但只包含非负数)。
因此,Sorbet 和 Gelato 决定找出可以加密的字典序最小消息是什么。帮助他们解决问题。
输入:
第一行包含一个整数 n (1 ≤ n ≤ 300000) —消息长度。
第二行包含n个整数A
1, A
2, ..., A
n (0 ≤ 艾 < 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),所有这些在字典序上都比最优解大。