Mô tả và yêu cầu

Cho một mảng 𝐴 cố định gồm 2𝑛 số nguyên 𝐴0, 𝐴1 … ,𝐴2𝑛−1. Gọi 𝑖 là tập con của 𝑥
nếu 𝑥 & 𝑖 = 𝑖.
Yêu cầu: ∀𝑥 = 0..2𝑛 − 1 tính hàm 𝐹 (𝑥) = Tổng của tất cả 𝐴[𝑖] sao cho 𝑖 là tập con
của 𝑥, cụ thể:
𝐹[𝑥] = ∑𝑖 & 𝑥=𝑖 𝐴[𝑖] với 𝑥 = 0..2𝑛 − 1.

Dữ liệu vào

- Dòng đầu chứa số nguyên dương 𝑛 (𝑛 ≤ 20)
- Dòng tiếp theo chứa 2𝑛 số nguyên 𝐴0, 𝐴1 … ,𝐴2𝑛−1 (−109 ≤ 𝐴𝑖 ≤ 109).
Kết quả ra:
Ghi 1 dòng chứa 2𝑛 số nguyên, số nguyên thứ 𝑖 là 𝐹[𝑖] tương ứng.

Ví dụ

INPUT                        OUTPUT
                   3                             1 3 4 10 6 14 16 36
                   1 2 3 4 5 6 7 8
Giải thích: Ta có:
𝐹[0]  = 𝐴0= 1
𝐹[1]  = 𝐴0  +  𝐴1 =  1 +  2 =  3  (vì 0=002, 1=012 là tập con của 1= 012)
𝐹[2]  = 𝐴0  +  𝐴2 =  1 +  3 =  4 (vì 0=002, 2=102 là tập con của 2=102)
𝐹[3]  = 𝐴0  +  𝐴1 +  𝐴2 +  𝐴3  =  1 +  1 + 3  + 4  = 10 (vì 0  =  002, 1  =  012, 2 =  102,
               3 =  112là tập con của 3    =  112)
…
𝐹[7]  = 𝐴0  +  𝐴1 +  𝐴2 +  𝐴3  + 𝐴4  +  𝐴5 +  𝐴6  + 𝐴7  =  1 +  2 + 3  + 4 +  5 +  6 +  7 +
8 =  36 (vì 0 =  0002,  1 =  0012,  2 =  0102,   3 =  0112,  4 =  1002,  5 =  1012,  6 =
1102, 7  = 1112 là tập con của 7=1112)