問題文

長さ $2^N$ の整数列 $A = (A_0, A_1, \dots, A_{2^N-1}), B = (B_0, B_1, \dots, B_{2^N-1})$ が与えられます。 $$\begin{aligned} C_k = \left( \sum_{i=0}^{2^N-1} A_i B_{i \& k} \right) \bmod 998244353 \end{aligned}$$ により定義される長さ $2^N$ の数列 $C = (C_0, C_1, \dots, C_{2^N-1})$ を計算してください。 ただし $\&$ は bitwise and を表します。

制約

• $0 \leqq N \leqq 20$
• $0 \leqq A_i \lt 998244353\ \ $($0 \leqq i \lt 2^N$)
• $0 \leqq B_i \lt 998244353\ \ $($0 \leqq i \lt 2^N$)

入力

$N$
$A_0\ \ A_1\ \ \cdots\ \ A_{2^N-1}$
$B_0\ \ B_1\ \ \cdots\ \ B_{2^N-1}$

出力

$C_0\ \ C_1\ \ \cdots\ \ C_{2^N-1}$

$C$ の各要素を一行に空白区切りで出力してください。 最後に改行してください。

サンプル

2
2 3 4 4
5 3 2 4

65 51 41 43

0
4
1

4

1
1 998244352
998244352 1

0 998244351