Module: 贪心算法


Problem

9 /9


Sorbet 和 Gelato 加密了消息

Problem

Sorbet 和 Gelato 学到了重要的数据。这些数据是不能公开的秘密,但体积之大,根本不可能完全记住。所以他们决定加密它们。

Sorbet 从数据中编辑了一条信息。数字化后,消息是一个由 n 个非负整数组成的序列 M。为了加密,Sorbet 生成了一个随机密钥 K,它也是一个由 n 个非负整数组成的序列。
之后,它将加密消息 A 计算为原始消息的每个相应元素和密钥的按位异或 (Ai = Mi ⊕ K我) .
Sorbet 为自己保留了加密信息,为了确保安全,密钥被发送给了 Gelato,他将其删除。然而,传输通道被证明是不可靠的,Gelato 收到了密钥 P,其中交换了来自 K 的一些元素。也就是说,我得到了原始密钥 K 的一些排列。

当需要解码回信息时,他们惊恐地意识到了这个问题。然而,Sorbet 记得原始消息在字典上非常小(但只包含非负数)。
因此,Sorbet 和 Gelato 决定找出可以加密的字典序最小消息是什么。帮助他们解决问题。

输入:
第一行包含一个整数 n (1 ≤ n ≤ 300000) —消息长度。
第二行包含n个整数A1, A2, ..., An (0 ≤  艾 < 230) —加密信息。
第三行包含n个整数P1, P2, ..., Pn (0 ≤  Pi < 230) —其元素被任意重新排列的加密密钥。

输出:
用 n 个整数打印一行 —字典序最小的可能原始消息。回想一下,其中的所有数字都必须是非负数。

示例:
  <正文>
解释:
在第一个例子中,解是 (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),所有这些在字典序上都比最优解大。
输入 输出
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