Дано число \(N\) та масив з \(2^N\) чисел (нумерація масиву починається з 0)

Для кожного \(X\) від \(0\) до \(2^N - 1\) порахуйте \(F(X)\)

\(F(X) = SUM(A[submask])\) - де \(submask\) - це всі можливі бітові підмаски двійкового представлення числа \(X\)

Формат вхідних даних

В першому рядку ціле число \(N\). (\(1<=N<= 20\))
В наступному рядку міститься \(2^N\) цілих чисел \(Ai\) (\(0 \le Ai \le 1000\))

Формат вихідних даних

Виведіть \(2^N\) чисел - відповідь \(F(X)\) для кожного \(X\) від \(0\) до \(2^N-1\)

Приклад вхідних даних

2
1 1 2 2

Приклад вихідних даних

1 2 3 6

Пояснення

Для прикладу

0 1 2 3
-------
1 1 2 2

F(0) = A[0] 
F(1) = A[0]+A[1]
F(2) = A[0]+A[2]
F(3) = A[0]+A[1]+A[2]+A[3]