题目描述

Alice 有一条非常重要的信息 $M$，由一些非负整数组成，她希望将其保密，不让 Eve 知道。Alice 知道，唯一理论上安全的加密方式是一次性密码本。Alice 生成了一个长度与消息相同的随机密钥 $K$。Alice 计算消息和密钥每个元素的按位异或（即 $A_i = M_i \oplus K_i$，其中 $\oplus$ 表示按位异或运算），并将这个加密后的消息 $A$ 保存下来。Alice 很聪明。像 Alice 一样吧。

例如，Alice 可能想要保存的信息是 $M=(0,15,9,18)$。她生成的密钥为 $K=(16,7,6,3)$。因此加密后的消息为 $A=(16,8,15,17)$。

Alice 意识到不能将密钥和加密消息一起保存。她把密钥 $K$ 发送给了 Bob，并删除了自己的副本。Alice 很聪明。真的，像 Alice 一样吧。

Bob 意识到加密消息只有在密钥保密的情况下才是安全的。因此，Bob 在保存密钥之前随机打乱了密钥的顺序。Bob 认为这样，即使 Eve 得到了加密消息和密钥，也无法读取消息。Bob 不聪明。不要像 Bob 一样。

在上面的例子中，Bob 可能选择了一个排列 $(3,4,1,2)$，并保存了打乱后的密钥 $P=(6,3,16,7)$。

一年过去了，Alice 想要解密她的信息。直到现在 Bob 才意识到这是不可能的。由于他随机打乱了密钥，消息永远丢失了。我们提到过 Bob 不聪明吗？

Bob 希望至少能从消息中挽救一些信息。由于他不太聪明，他向你求助。你知道加密消息 $A$ 和打乱后的密钥 $P$。请你找出可能得到该加密消息的字典序最小的消息。

更准确地说，给定 $A$ 和 $P$，请你找出字典序最小的消息 $O$，使得存在一个排列 $\pi$，满足对于每个 $i$，$O_i = A_i \oplus P_{\pi_i}$。

注意，如果存在某个下标 $i$，使得 $S_i < T_i$，且对于所有 $j < i$ 都有 $S_j = T_j$，则序列 $S$ 的字典序小于序列 $T$。

输入格式

第一行包含一个整数 $N$（$1 \leq N \leq 300000$），表示消息的长度。

第二行包含 $N$ 个整数 $A_1, A_2, \ldots, A_N$（$0 \leq A_i < 2^{30}$），表示加密后的消息。

第三行包含 $N$ 个整数 $P_1, P_2, \ldots, P_N$（$0 \leq P_i < 2^{30}$），表示打乱后的密钥。

输出格式

输出一行 $N$ 个整数，表示字典序最小的可能消息 $O$。注意，所有元素都应为非负数。

说明/提示

在第一个样例中，答案为 $(10,3,28)$，因为 $10 = 15 \oplus 5$，$3 = 8 \oplus 11$，$28 = 17 \oplus 13$。密钥的其他排列会得到消息 $(25,6,10)$、$(25,3,15)$、$(10,21,10)$、$(15,21,15)$ 和 $(15,6,28)$，这些消息的字典序都大于答案。

由 ChatGPT 4.1 翻译

样例

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
331415699 278745619 998190004 423175621 42983144 166555524 843586353 802130100 337889448 685310951
226011312 266003835 342809544 504667531 529814910 684873393 817026985 844010788 993949858 1031395667

128965467 243912600 4281110 112029883 223689619 76924724 429589 119397893 613490433 362863284