Trans

밥은 팝카운트(popcount)와 특이한 변환에 관심이 있다. 현재 그는 다음 문제를 풀고 있다.

길이가 $2^n$인 정수 배열 $a_0,a_1,a_2,\ldots,a_{2^n-1}$이 있다. 각 $i$ ($0 \le i \le 2^n-1$)에 대해 아래 값 $b_i$를 구하라.

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

여기서 $\operatorname{popcount}(x)$는 $x$를 이진수로 나타냈을 때 1의 개수이고, $\operatorname{and}$는 비트 AND 연산이다.

밥은 아주 똑똑하지만 이 문제를 빠르게 풀지 못한다. 모든 $b_i$를 계산하는 것을 도와주겠는가?

첫 줄에 정수 $n$ ($1 \le n \le 20$)이 주어진다.

둘째 줄에는 배열 $a$를 나타내는 $2^n$개의 정수가 주어진다 ($1 \le a_i \le 10^9$).

$2^n$개의 정수를 한 줄에 출력한다. $i$번째 수는 $b_i$이다.