問題文

ファンタジーゲーム「クリスタルクロニクル」では、魔法石と呼ばれるアイテムが登場する。 魔法石は識別番号によって管理されており、識別番号は $0$ 以上 $2^N$ 未満の整数である。 つまり、魔法石は全部で $2^N$ 種類存在する。

各魔法石 $i$（$0 \le i < 2^N$）には 魔力値 $c_i$ が設定されている。

魔法使いは、この $2^N$ 種類の魔法石から好きな部分集合（空集合を含む）を選んで 魔法陣を構成する。魔法陣の 共鳴値 は、 選んだ全ての魔法石の識別番号の排他的論理和（XOR）で定まる。 何も選ばなかった場合の共鳴値は $0$ とする。

各共鳴値 $T$（$0 \le T < 2^N$）に対して、次の値を求めよ：

$g_T = \sum_{\substack{S \subseteq \{0, 1, \ldots, 2^N - 1\} \\ \bigoplus_{i \in S} i = T}} \prod_{i \in S} c_i$

ただし、空集合の積は $1$ とする。

答えは非常に大きくなりうるので、$998244353$ で割った余りを出力せよ。

制約

• $1 \le N \le 18$
• $0 \le c_i < 998244353$（$0 \le i < 2^N$）
• 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる．

出力

$2^N$ 個の整数 $g_0,\ g_1,\ \ldots,\ g_{2^N - 1}$ を空白区切りで 1 行に出力せよ。

サンプル

2
1 2 3 4

50 28 22 20

$N=2$ なので魔法石は 4 種類（識別番号 $0, 1, 2, 3$）、魔力値はそれぞれ $1, 2, 3, 4$。 全 $16$ 通りの部分集合を列挙する：

各共鳴値ごとに積を合計：

• $g_0 = 1+1+24+24 = 50$
• $g_1 = 2+2+12+12 = 28$
• $g_2 = 3+3+8+8 = 22$
• $g_3 = 4+4+6+6 = 20$