CF1034E.Little C Loves 3 III

Little C loves number «3» very much. He loves all things about it.

Now he is interested in the following problem:

There are two arrays of $2^n$ intergers $a_0,a_1,...,a_{2^n-1}$ and $b_0,b_1,...,b_{2^n-1}$.

The task is for each $i (0 \leq i \leq 2^n-1)$, to calculate $c_i=\sum a_j \cdot b_k$ ($j|k=i$ and $j\&k=0$, where "$|$" denotes bitwise or operation and "$\&$" denotes bitwise and operation).

It's amazing that it can be proved that there are exactly $3^n$ triples $(i,j,k)$, such that $j|k=i$, $j\&k=0$ and $0 \leq i,j,k \leq 2^n-1$. So Little C wants to solve this excellent problem (because it's well related to $3$) excellently.

Help him calculate all $c_i$. Little C loves $3$ very much, so he only want to know each $c_i \& 3$.

小 C 非常喜欢数字「3」，他对所有与之相关的事物都情有独钟。

现在他感兴趣的问题如下：

给定两个长度为 $2^n$ 的整数数组：$a_0, a_1, \dots, a_{2^n-1}$ 和 $b_0, b_1, \dots, b_{2^n-1}$。

任务是：对每个 $i$（其中 $0 \leq i \leq 2^n-1$），计算

$$c_i = \sum a_j \cdot b_k,$$

其中求和遍历所有满足 $j|k=i$ 且 $j\&k=0$ 的下标对 $(j,k)$；这里 "$|$" 表示按位或运算，"$\&$" 表示按位与运算。

令人惊奇的是，可以证明：满足 $j|k=i$、$j\&k=0$ 且 $0 \leq i,j,k \leq 2^n-1$ 的三元组 $(i,j,k)$ 恰好有 $3^n$ 个。因此，小 C 希望出色地解决这个卓越的问题（因为它与数字 $3$ 密切相关）。

请帮助他计算出所有的 $c_i$。小 C 非常喜爱数字 $3$，所以他只关心每个 $c_i \& 3$ 的值。

The first line contains one integer $n (0 \leq n \leq 21)$.

The second line contains $2^n$ integers in $[0,3]$ without spaces — the $i$-th of them is $a_{i-1}$.

The third line contains $2^n$ integers in $[0,3]$ without spaces — the $i$-th of them is $b_{i-1}$.

第一行包含一个整数 $n (0 \leq n \leq 21)$。

第二行包含 $2^n$ 个在 $[0,3]$ 范围内的整数，中间无空格——其中第 $i$ 个数为 $a_{i-1}$。

第三行包含 $2^n$ 个在 $[0,3]$ 范围内的整数，中间无空格——其中第 $i$ 个数为 $b_{i-1}$。

Print one line contains $2^n$ integers in $[0,3]$ without spaces — the $i$-th of them is $c_{i-1}\&3$. (It's obvious that $c_{i}\&3$ is in $[0,3]$).

输出一行，包含 $2^n$ 个在 $[0,3]$ 范围内的整数，中间不加空格——其中第 $i$ 个数为 $c_{i-1}\&3$。（显然 $c_{i}\&3$ 的值在 $[0,3]$ 范围内）