Problem
셔벗과 젤라또는 중요한 데이터를 배웠습니다. 이 데이터는 공개할 수 없는 비밀이지만 그 양이 너무 커서 완전히 기억할 수 없었습니다. 그래서 그들은 그것들을 암호화하기로 결정했습니다.
셔벗은 데이터에서 메시지를 컴파일했습니다. 디지털화 후 메시지는 음이 아닌 정수 n개의 시퀀스 M이었습니다. 암호화를 위해 Sorbet은 임의의 키 K를 생성했으며 이 키 역시 n개의 음이 아닌 정수 시퀀스였습니다.
그런 다음 암호화된 메시지 A를 원본 메시지의 각 해당 요소와 키의 비트별 XOR로 계산했습니다(A
i = M
i + K
i) .
Sorbet은 암호화된 메시지를 자신을 위해 보관했으며 보안을 위해 키를 Gelato로 전송하고 지웠습니다. 그러나 전송 채널이 신뢰할 수 없는 것으로 판명되었고 Gelato는 K의 일부 요소가 교체된 키 P를 받았습니다. 즉, 원래 키 K의 일부 순열을 얻었습니다.
메시지를 다시 해독할 때가 되었을 때 그들은 문제를 깨닫고 겁을 먹었습니다. 그러나 Sorbet은 원래 메시지가 사전적으로 매우 작다는 것을 기억했습니다(그러나 음수가 아닌 숫자만 포함됨).
그래서 Sorbet과 Gelato는 암호화할 수 있는 사전식으로 가장 작은 메시지가 무엇인지 알아내기로 했습니다. 그들이 그것을 알아낼 수 있도록 도와주세요.
입력:
첫 번째 줄에는 단일 정수 n(1 ≤ n ≤ 300000)이 포함되어 있습니다. 메시지 길이.
두 번째 줄에는 n개의 정수 A
1, A
2, ..., A
n (0 ≤ Ai < 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)입니다. 2 = 10, 4 ± 7 = 3 및 13 + 17 = 28.
다른 가능한 키 순열은 (25, 6, 10), (25, 3, 15), (10, 21, 10), (15, 21, ;15) 및 (15, 6, 28), 이들은 모두 최적 솔루션보다 사전식으로 더 큽니다.