Hai Chỉ Số Tốt Nhất · canuc80k4614

Cho dãy $A$ được đánh chỉ số từ $0$ đến $2^{N} - 1$ . Với mỗi số nguyên $K$ từ $1$ đến $2^{N} - 1$ , xét mọi cặp chỉ số $i < j$ thỏa $(i ∣ j) \leq K$ , trong đó | là OR bit. Hãy tìm giá trị lớn nhất của $A_{i} + A_{j}$ .

Input

Dòng đầu chứa $N$ . Dòng thứ hai chứa $2^{N}$ số $A_{0}, A_{1}, \dots, A_{2^{N} - 1}$ .

Output

In $2^{N} - 1$ dòng. Dòng thứ $K$ là đáp án ứng với giá trị $K$ .

Constraints

$1 \leq N \leq 18$ .
$1 \leq A_{i} \leq 1 0^{9}$ .

Scoring

Subtask $1$ ( $50%$ số điểm): $N \leq 8$ .
Subtask $2$ ( $50%$ số điểm): Không có giới hạn bổ sung.

Example

Test 1

Input

2
1 4 2 3

Output

5
5
7

Giải thích: Với $K = 1$ , chỉ cặp chỉ số $0, 1$ hợp lệ nên đáp án là $5$ . Với $K = 2$ , cặp $0, 1$ vẫn tốt nhất và cho $5$ ; với $K = 3$ , hai giá trị lớn nhất là $4, 3$ , cho $7$ .

Phân tích: Với một mask m, điều kiện i|j là submask của m tương đương cả i và j đều là submask của m. Vì vậy chỉ cần biết hai giá trị lớn nhất ở các chỉ số submask của từng m. Điều kiện đề là bất đẳng thức số i|j≤K, nên sau đó phải lấy prefix maximum theo giá trị mask, không chỉ dùng riêng mask K.
Thuật toán: Mỗi trạng thái ban đầu giữ cặp (A_m,m). Chạy subset SOS, khi gộp chỉ giữ hai ứng viên có chỉ số khác nhau và giá trị lớn nhất. Gọi best[m] là tổng hai ứng viên của trạng thái m. Duyệt K=1..2^N-1, duy trì answer=max(answer,best[K]) và in prefix maximum.
Chứng minh đúng đắn: Sau SOS, trạng thái m đã nhận đúng mọi chỉ số submask của m; giữ hai giá trị lớn nhất là đủ để tối đa tổng của hai chỉ số phân biệt. Do đó best[m] là tốt nhất trong các cặp có i|j subseteq m, và đặc biệt mọi cặp có OR đúng m được xét tại trạng thái m.
Chứng minh đúng đắn: Một cặp hợp lệ cho truy vấn K có r=i|j≤K, nên xuất hiện trong best[r] và được prefix maximum xét. Ngược lại, mọi cặp tạo ra bởi best[m] với m≤K có i|j subseteq m, suy ra i|j≤m≤K, nên hợp lệ. Hai phía trùng nhau, vì vậy prefix maximum là đáp án.
Độ phức tạp: O(N·2^N) thời gian và O(2^N) bộ nhớ.