Problem
ソルベとジェラートは重要なデータを学びました。このデータは公開できない秘密ですが、その量が多すぎて完全に記憶することは不可能でした。そこで暗号化することに
しました。
ソルベ氏はデータからメッセージをまとめた。デジタル化後のメッセージは、n 個の非負の整数のシーケンス M でした。暗号化のために、Sorbet はランダムなキー K を生成しました。これも n 個の非負の整数のシーケンスでした。
その後、暗号化されたメッセージ A を、元のメッセージの対応する各要素とキーのビットごとの XOR として計算しました (A
i = M
i ⊕ K
私) 。
ソルベは暗号化されたメッセージを自分用に保管し、セキュリティを確保するためにキーをジェラートに送信し、ジェラートがそれを消去しました。しかし、伝送チャネルは信頼できないことが判明し、ジェラートは K の要素の一部が交換された鍵 P を受け取りました。つまり、元のキー K の順列が得られ
ました。
メッセージを解読する段階になったとき、彼らは問題を認識して愕然としました。しかし、Sorbet は、元のメッセージが辞書編集的に非常に小さいことを思い出しました (ただし、負ではない数字のみが含まれていました)。
そこで、Sorbet と Gelato は、暗号化できる辞書編集上の最小のメッセージが何かを調べることにしました。彼らがそれを理解できるように手助けしてください。
入力:
最初の行には、単一の整数 n (1≤ n ≤ 300000) が含まれています。メッセージの長さ
2 行目には、n 個の整数 A1、 A2、 ...、 An (0 ≤) が含まれています。 Ai < 230) —暗号化されたメッセージ
3 行目には、n 個の整数 P1、 P2、 ...、 Pn (0 ≤ Pi < 230) —要素を任意に並べ替えた暗号化キー
です。
出力:
n 個の整数を 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 |
説明:
最初の例では、8 &oplus であるため、解は (10,≡3,≠28) になります。 2 = 10、4⊕ 7 = 3 と 13 ⊕ 17 = 28。
他の可能なキーの置換では、メッセージ (25, 6, 10)、(25, 3, 15)、(10, 21, 10)、(15, 21, ;15) および (15, 6, 28) であり、これらはすべて最適解よりも辞書編集的に大きくなっています。