Trong khu bảo tồn có \(N = 2^K\) loài sinh vật, mỗi loài được đánh mã số từ 0 đến \(N-1\). Người ta phát hiện ra rằng loài mã số \(x\) là "tiền thân" của loài mã số \(y\) nếu mọi đặc điểm di truyền của \(x\) đều có trong y (viết là \(x \subseteq y\)).

Với mỗi loài \(mask\), hãy tính tổng số lượng cá thể của tất cả các loài tiền thân của nó. Nói cách khác, tính \(G[mask] = \sum_{x \subseteq mask} A[x]\).

Đầu vào:

• Dòng 1: hai số nguyên \(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:

• Một dòng gồm \(N\) số nguyên là \(G[mask]\) cho mọi \(mask = 0..N-1\).

Ví dụ: \(N=4, K=2, A=[1,2,3,4]\) → \(G[0]=1, G[1]=1+2=3, G[2]=1+3=4, G[3]=1+2+3+4=10\).

#

Đị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 là \(\sum_{j \subseteq i} A[j]\).

Ví dụ

Input:

2
1 2 3 4

Output:

1 3 4 10

Giải thích: Với mask 0: 1; mask 1: 1+2=3; mask 2: 1+3=4; mask 3: 1+2+3+4=10.

Ràng buộc & Subtasks