Cho một mảng ~A~ cố định gồm ~2^n~ số nguyên ~A[0], A[1], ... , A[2^n-1]~. Gọi ~i~ là tập con của ~x~ nếu ~x \ \& \ i = i~.

Yêu cầu: Với mọi ~x = \overline{0, 2^n - 1}~ tính hàm ~F(x) =~ Tổng của tất cả ~A[i]~ sao cho ~i~ là tập con của ~x~, cụ thể:

$$F[𝑥] = \sum_{i \ \& \ x = i} A[i], x = \overline{0, 2^n - 1}$$.

Dữ liệu vào:

• Dòng đầu chứa số nguyên dương ~n~ ~(n ≤ 20)~.
• Dòng tiếp theo chứa ~2^n~ số nguyên ~A_0, A_1, ... , A_{2^n-1}~ ~(-10^9 ≤ A_i ≤ 10^9)~.

Kết quả ra: Ghi ~1~ dòng chứa ~2^n~ số nguyên, số nguyên thứ ~i~ là ~F[i]~ tương ứng.

Ví dụ:

SOSDP.INP

3
1 2 3 4 5 6 7 8

SOSDP.OUT

1 3 4 10 6 14 16 36

Giải thích: Ta có:

• ~F[0] = A_0 = 1~

• ~F[1] = A_0 + A_1 = 1 + 2 = 3~ (vì ~0 = (00)_2~, ~1 = (01)_2~ là tập con của ~1 = (01)_2~)

• ~F[2] = A_0 + A_2 = 1 + 3 = 4~ (vì ~0 = (00)_2~, ~2 = (10)_2~ là tập con của ~2 = (10)_2~)

• ~F[3] = A_0 + A_1 + A_2 + A_3 = 1 + 2 + 3 + 4 = 10~
  (vì ~0 = (00)_2~, ~1 = (01)_2~, ~2 = (10)_2~, ~3 = (11)_2~ là tập con của ~3 = (11)_2~)

• ...

• ~F[7] = A_0 + A_1 + A_2 + A_3 + A_4 + A_5 + A_6 + A_7 = 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 = 36~
  (vì ~0 = (000)_2~, ~1 = (001)_2~, ~2 = (010)_2~, ~3 = (011)_2~, ~4 = (100)_2~, ~5 = (101)_2~, ~6 = (110)_2~, ~7 = (111)_2~ là tập con của ~7 = (111)_2~)