Tý có một công ty có \(N = 2^K\) nhân viên, mỗi nhân viên có mã số từ 0 đến \(N-1\) và năng suất \(A[i]\). Giám đốc muốn chọn ra một nhóm làm việc. Một nhân viên mã \(x\) có thể dẫn dắt nhân viên \(y\) nếu \(x\) là tiền thân của y (\(x \subseteq y\)).

Với mỗi nhân viên \(mask\), hãy tìm năng suất lớn nhất trong số các nhân viên mà \(mask\) có thể dẫn dắt (kể cả chính \(mask\)). Nói cách khác, tính \(G[mask] = \max_{x \subseteq mask} A[x]\).

Đầu vào:

• Dòng 1: \(N, K\) (\(N = 2^K, K \le 20\))
• Dòng 2: \(N\) số nguyên \(A[0..N-1]\) (\(0 \le A[i] \le 10^9\))

Đầu ra:

• \(N\) số nguyên \(G[mask]\) với mọi \(mask = 0..N-1\).

#

Định dạng đầu vào

• Dòng 1: Số nguyên \(K\) (\(1 \le K \le 20\)).
• Dòng 2: \(2^K\) số nguyên \(A[0], A[1], \dots, A[2^K-1]\) (\(0 \le A[i] \le 10^9\)).

Định dạng đầu ra

• \(2^K\) số nguyên trên một dòng, số thứ i (\(0 \le i < 2^K\)) là giá trị lớn nhất trong tất cả \(A[j]\) với \(j \subseteq i\).

Ví dụ

Input:

2
1 4 2 5

Output:

1 4 2 5

Giải thích: Với mask 3 (\(11_2\)), các tập con là 0, 1, 2, 3 với các giá trị 1, 4, 2, 5 -> max là 5.

Ràng buộc & Subtasks