Problem
Sorbet và Gelato đã học được dữ liệu quan trọng. Dữ liệu này là một bí mật không thể tiết lộ, nhưng khối lượng của chúng quá lớn nên không thể nhớ hết chúng. Vì vậy, họ quyết định mã hóa chúng.
Sorbet biên soạn một tin nhắn từ dữ liệu. Sau khi số hóa, tin nhắn là một dãy M gồm n số nguyên không âm. Để mã hóa, Sorbet đã tạo một khóa K ngẫu nhiên, khóa này cũng là một dãy n số nguyên không âm.
Sau đó, nó tính toán thông báo được mã hóa A dưới dạng XOR từng bit của từng phần tử tương ứng của thông báo gốc và khóa (A
i = M
i ⊕ K
tôi).
Sorbet giữ tin nhắn được mã hóa cho riêng mình và để đảm bảo tính bảo mật, chìa khóa đã được gửi cho Gelato và anh ta đã xóa nó. Tuy nhiên, kênh truyền hóa ra không đáng tin cậy và Gelato đã nhận được khóa P, trong đó một số phần tử từ K đã bị tráo đổi. Đó là, tôi đã nhận được một số hoán vị của khóa ban đầu K.
Đến lúc giải mã lại tin nhắn, họ mới kinh hoàng nhận ra vấn đề. Tuy nhiên, Sorbet nhớ rằng tin nhắn ban đầu khá nhỏ về mặt từ điển (nhưng chỉ chứa các số không âm).
Vì vậy, Sorbet và Gelato quyết định tìm ra thông điệp nhỏ nhất về mặt từ điển có thể được mã hóa là gì. Hãy giúp họ tìm ra.
Đầu vào:
Dòng đầu tiên chứa một số nguyên n (1 ≤ n ≤ 300000) — độ dài tin nhắn.
Dòng thứ hai chứa n số nguyên A
1, A
2, ..., A
n (0 ≤ Ai < 2
30) — tin nhắn được mã hóa.
Dòng thứ ba chứa n số nguyên P
1, P
2, ..., P
n (0 ≤ Pi < 2
30) — một khóa mã hóa có các phần tử được sắp xếp lại tùy ý.
Đầu ra:
In một dòng có n số nguyên — thông điệp gốc nhỏ nhất có thể về mặt từ điển. Nhắc lại rằng tất cả các số trong đó phải không âm.
Ví dụ:
| Đầu vào |
Đầu ra |
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 |
Giải thích:
Trong ví dụ đầu tiên, giải pháp là (10, 3, 28) vì 8 ⊕ 2 = 10, 4 ⊕ 7 = 3 và 13 ⊕ 17 = 28.
Các hoán vị khóa có thể khác cho các thông báo (25, 6, 10), (25, 3, 15), (10, 21, 10), (15, 21, ;15) và (15, 6, 28), tất cả đều lớn hơn về mặt từ điển so với giải pháp tối ưu.