UOJ Logo

NOI.AC

1S 512MB
Statistics

知识点

要考NOIP了。

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

输入长度为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<=220,0<=a[i]<=1000

对于30%的数据,满足1<=n<=210

对于70%的数据,满足1<=n<=215