Cho dãy số nguyên không âm. Với mỗi phần tử, hãy chọn một giá trị xuất hiện trong dãy sao cho hai giá trị không có bit 1 chung. Có thể chọn chính lần xuất hiện đang xét. Nếu không có giá trị phù hợp, trả −1.
Input
Dòng đầu chứa n. Dòng thứ hai chứa n số nguyên a1,a2,…,an.
Output
In n số. Số thứ i là một giá trị xuất hiện trong dãy và thỏa aiANDx=0; nếu không tồn tại thì in −1. Khi có nhiều đáp án, được phép in bất kỳ đáp án hợp lệ nào.
Constraints
1≤n≤106.
0≤ai<222.
Scoring
Subtask 1 (50% số điểm): n≤2000 và ai<212.
Subtask 2 (50% số điểm): Không có giới hạn bổ sung.
Example
Test 1
Input
5
1 2 3 4 7
Output
4 4 4 3 -1
Giải thích: Các lựa chọn trong output đều hợp lệ vì 1AND4=2AND4=3AND4=0 và 4AND3=0. Với 7, mọi giá trị trong dãy đều có ít nhất một bit 1 chung, nên đáp án cuối là −1.
Lời giải tóm tắt
Phân tích: Ta cần một giá trị xuất hiện trong dãy và chỉ dùng các bit mà a_i không dùng. Nói cách khác, witness phải là một submask của ALL xor a_i. Vì chỉ cần trả về một witness bất kỳ, mỗi trạng thái chỉ cần lưu một giá trị đại diện thay vì số lượng.
Thuật toán: Khởi tạo any[m]=m nếu mask m xuất hiện, ngược lại bằng -1. Chạy subset SOS: với từng bit, nếu any[m] chưa có witness thì kế thừa any[m bỏ bit]. Sau biến đổi, any[m] là một giá trị xuất hiện và là submask của m, hoặc -1 nếu không tồn tại. Với mỗi a_i, trả any[ALL xor a_i].
Chứng minh đúng đắn: Bất biến của subset SOS là sau khi xử lý một tập bit, any[m] chứa một mask xuất hiện có thể nhận được từ m bằng cách bỏ các bit đã xử lý. Kết thúc mọi bit, tập ứng viên chính xác là toàn bộ submask của m; do đó any[m] tồn tại đúng khi có ít nhất một giá trị xuất hiện là submask của m.
Chứng minh đúng đắn: Với m=ALL xor a_i, mọi submask x của m không có bit 1 chung với a_i, nên a_i & x=0. Ngược lại, mọi witness thỏa AND bằng 0 đều chỉ dùng bit thuộc m và là submask của m. Vì vậy giá trị trả về hoặc -1 là đúng; checker cho phép mọi witness hợp lệ.
Độ phức tạp:O(n + B·2^B) thời gian và O(2^B) bộ nhớ, với B≤22.