24713번 - Trans 다국어

문제

Bob is interested in popcount and some strange transforms. Currently, he is attacking the following problem:

There is an array of 2ドル^n$ integers $a_0,a_1,a_2,\ldots,a_{2^n-1}$. The task is, for each $i$ (0ドル \le i \le 2^n-1$), to calculate

$$b_i=\sum\limits_{j=0}^{2^n-1} (\operatorname{popcount}(i ,円 \operatorname{and} ,円 j) \bmod 2) \cdot a_j\text{,}$$

where "$\operatorname{popcount}(x)$" denotes the number of ones in the binary representation of $x,ドル and "$\operatorname{and}$" denotes the bitwise AND operation.

Although Bob is very smart, he still can't solve the problem fast. Can you help him calculate all $b_i$?

입력

The first line contains a single integer $n$ (1ドル \le n \le 20$).

The second line contains 2ドル^n$ integers describing the array $a$ (1ドル \le a_i \le 10^9$).

출력

Print one line with 2ドル^n$ integers, the $i$-th of them being the value $b_i$.

제한

힌트