当前没有测试数据。

题目描述

伊有一个数组 a，它的长度为 2^n，下标从 0 开始到2^n-1结束。

如果把 j和 i 同时转为二进制之后，对于j所有为 1 的二进制位，i对应的二进制位都为 1，那么称 j 是 i 的子集。

比如二进制 010 就是二进制 110 的子集，而二进制 011 就不是二进制 110 的子集，二进制11 是二进制 11 的子集。

伊要求一个同样长度的数组 b，其中 b[i] 是“是 i 的子集”的 j 对应的 a[j] 的和。

输入格式

第一行一个整数 n表示数组 a 的长度为 2^n。

接下来 2^n个数，表示数组 a。

输出格式

一行2^n 个数表示数组 b。

样例

输入#1

2
1 2 3 4

输出#1

1 3 4 10

解释

数据范围/约定

对于 20% 的数据，n ≤ 10。

对于 40% 的数据, n ≤ 15。

对于另外 20% 的数据，满足a[i] = 1。