← 返回题目列表

Codeforces · 923/C

C. 完美的安全性

中文机器翻译题面 查看原题

Alice 有一条非常重要的消息 M,其中包含一些非负整数,她想对 Eve 保密。爱丽丝知道理论上唯一安全的密码是一次性密码本。 Alice 生成一个随机密钥 K,其长度等于消息的长度。 Alice 计算消息的每个元素和密钥的按位异或($$A_i := M_i \oplus K_i$$,其中 $$\bigcirc$$ 表示按位异或运算)并存储此加密消息 A。Alice 很聪明。像爱丽丝一样。

例如,Alice 可能想要存储消息 M = (0, 15, 9, 18)。她生成了一个密钥 K = (16,7,6,3)。因此,加密消息为 A = (16, 8, 15, 17)。

Alice 意识到她无法将密钥与加密消息一起存储。 Alice 将她的密钥 K 发送给 Bob,并删除了她自己的副本。爱丽丝很聪明。真的,像爱丽丝一样。

Bob 意识到,只有密钥是秘密的,加密消息才是安全的。因此,鲍勃在存储密钥之前随机排列了密钥。 Bob认为这样一来,即使Eve同时获得了加密消息和密钥,她也无法读取该消息。鲍勃并不聪明。别像鲍勃一样。

在上面的示例中,Bob 例如可能选择了排列 (3, 4, 1, 2) 并存储了排列后的密钥 P = (6, 3, 16, 7)。

一年过去了,Alice 想要解密她的消息。直到现在鲍勃才意识到这是不可能的。由于他随机排列了密钥,消息就永远丢失了。我们有没有提到鲍勃不聪明?

Bob 希望从消息中至少抢救一些信息。因为他不太聪明,所以他请求你的帮助。您知道加密消息 A 和排列密钥 P。按字典顺序可以产生给定加密文本的最小消息是什么?

更准确地说,对于给定的 A 和 P,找到字典顺序最小的消息 O,其中存在一个排列 π,使得对于每个 i, $$O_{i} \oplus \pi(P_{i}) = A_{i}$$ 。

请注意,如果存在索引 i 使得 Si < Ti 并且对于所有 j < i,则条件 Sj = Tj 成立,则序列 S 按字典顺序小于序列 T。

输入

第一行包含一个整数 N (1 ≤ N ≤ 300000),即消息的长度。

第二行包含 N 个整数 A1、A2、...、AN (0 ≤ Ai < 230),表示加密消息。

第三行包含 N 个整数 P1、P2、...、PN (0 ≤ Pi < 230),表示排列后的加密密钥。

输出

输出包含 N 个整数的单行,即字典顺序上最小的可能消息 O。请注意,其所有元素都应该是非负的。

示例

输入 #1

3
8 4 13
17 2 7

输出 #1

10 3 28

输入 #2

5
12 7 87 22 11
18 39 9 12 16

输出 #2

0 14 69 6 44

输入 #3

10
331415699 278745619 998190004 423175621 42983144 166555524 843586353 802130100 337889448 685310951
226011312 266003835 342809544 504667531 529814910 684873393 817026985 844010788 993949858 1031395667

输出 #3

128965467 243912600 4281110 112029883 223689619 76924724 429589 119397893 613490433 362863284

注意

在第一种情况下,解为 (10, 3, 28),因为 $$8 \oplus 2 = 10$$、$$4 \oplus 7 = 3$$ 和 $$13 \oplus 17 = 28$$。密钥产生消息的其他可能排列 (25, 6, 10), (25, 3, 15), (10, 21, 10), (15, 21, 15) 和 (15, 6, 28),按字典顺序排列都比解大。