题目描述

对于所有的 $i$ ($0 \le i \leq 2^n - 1$)，求解 $\sum_{j = i\&j} a_j$（其中 $j \& i = j$ 表示 $j$ 是 $i$ 的子集，即 $j$ 的二进制表示中 1 的位置均在 $i$ 的二进制表示中出现）。

输入格式

• 第一行：整数 $n$
• 第二行：$2^n$ 个整数，其中第 $i$ 个数表示 $a_{i-1}$（即输入的第 1 个数对应 $a_0$，第 2 个数对应 $a_1$，...，第 $2^n$ 个数对应 $a_{2^n-1}$）。

输出格式

• 输出 $2^n$ 行，每行一个整数，第 $i$ 行（从 0 开始计数）的结果对应 $i$ 的答案。

输入示例

2
1 3 2 4

输出示例

1
4
3
10

数据范围

$n \leq 20, \, a_i \leq 10^6$