Bob 对 popcount 和一些奇怪的变换很感兴趣。目前，他正在攻克以下问题：

给定一个包含 $2^n$ 个整数的数组 $a_0, a_1, a_2, \dots, a_{2^n-1}$。任务是对于每个 $i$ ($0 \le i \le 2^n - 1$)，计算：

$$b_i = \sum_{j=0}^{2^n-1} (\text{popcount}(i \text{ and } j) \bmod 2) \cdot a_j$$

其中 “$\text{popcount}(x)$” 表示 $x$ 的二进制表示中 1 的个数，“and” 表示按位与运算。

尽管 Bob 非常聪明，但他仍然无法快速解决这个问题。你能帮他计算出所有的 $b_i$ 吗？

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 20$)。

第二行包含 $2^n$ 个整数，描述数组 $a$ ($1 \le a_i \le 10^9$)。

输出格式

输出一行，包含 $2^n$ 个整数，其中第 $i$ 个整数为 $b_i$ 的值。

样例

输入 1

2
1 2 3 4

输出 1

0 6 7 5