知识点

要考NOIP了。

NOIP一共要考k个知识点，考虑所有知识点的子集，共有$n=2^k$个。

输入长度为n的数组$a[i]$，下标从0开始，$a[i]$表示恰好掌握知识点集合i的人数。

其中$i$是一个子集，如果$i$的二进制第$j$位是1，那么表示这个集合包含知识点j，如果是$0$，表示不包含。

比如当k=6时，集合25的二进制是$011001$，从右向左，分别是第$1, 2, 3, 4, 5, 6$个知识点

所以$25$包含知识点${1, 4, 5}$，不包含知识点${2, 3, 6}$。

假设NOIP会考察知识点集合i，B君希望知道有多少人掌握的知识点集合，包含考察的知识点集合i。

对于每个知识点集合i，B君都想知道答案。

输入描述

第一行一个整数n，保证是2的次幂。

接下来n行n个整数，表示$a[i]$。

输出描述

输出共n行，其中第$i$($0 <= i < n$)行表示$i$的答案。

样例输入

8
128
64
32
16
8
4
2
1

样例输出

255
85
51
17
15
5
3
1

样例解释

i=0的答案 a[0] + a[1] + a[2] + a[3] + a[4] + a[5] + a[6] + a[7]

i=1的答案 a[1] + a[3] + a[5] + a[7]

i=2的答案 a[2] + a[3] + a[6] + a[7]

i=3的答案 a[3] + a[7]

i=4的答案 a[4] + a[5] + a[6] + a[7]

i=5的答案 a[5] + a[7]

i=6的答案 a[6] + a[7]

i=7的答案 a[7]

数据规模与约定

对于100%的数据，满足$1 <= n <= 2^{20}, 0 <= a[i] <= 1000$

对于30%的数据，满足$1 <= n <= 2 ^{10}$

对于70%的数据，满足$1 <= n <= 2^{15}$