問題文

すぬけくんはある乱数生成器を手に入れました。 この乱数生成器は、$0$ 以上 $2^N-1$ 以下の整数を生成します。 それぞれの整数を生成する確率は、整数列 $A_0,A_1,\\cdots,A_{2^N-1}$ によって表され、 整数 $i$ ($0 \\leq i \\leq 2^N-1$) が生成される確率は $A_i / S$ です。 ただしここで $S = \\sum_{i=0}^{2^N-1} A_i$ とします。 また、乱数生成は毎回独立に行われます。

すぬけくんは整数 $X$ を持っています。 今、$X=0$ です。 すぬけくんは、次の操作を好きなだけ行うことが出来ます。

• 乱数生成器で一つの整数 $v$ を生成する。そして、$X$ を $X \\oplus v$ で置き換える。 ただしここで、$\\oplus$ はビットごとの排他的論理和を表す。

それぞれの整数 $i$ ($0 \\leq i \\leq 2^N-1$) について、$X$ を $i$ にするために必要な操作の回数の期待値を求めてください。 ただし、期待値は mod $998244353$ で出力してください。 より正確には、期待値が既約分数 $P/Q$ で表されるとき、 $R \\times Q \\equiv P \\mod 998244353,\\ 0 \\leq R < 998244353$ を満たす整数 $R$ が一意に定まるので、その $R$ を出力してください。

なお、すべての $i$ について、$X$ を $i$ にするために必要な操作の回数の期待値が有理数として存在し、 さらに mod $998244353$ での整数表現が定義できることが問題の制約から証明できます。

制約

• $1 \\leq N \\leq 18$
• $1 \\leq A_i \\leq 1000$
• 入力される値はすべて整数である。

入力

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

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

出力

$2^N$ 行出力せよ。 $i+1$ 行目 ($0 \\leq i \\leq 2^N-1$) には、$X$ を $i$ にするために必要な操作の回数の期待値を mod $998244353$ で出力せよ。

入力例 1

2
1 1 1 1

出力例 1

0
4
4
4

$0$ 回操作をした段階で $X=0$ なので、$X$ を $0$ にするのに必要な操作回数の期待値は $0$ です。

また、どの状態から操作しても、操作後の $X$ の値はそれぞれ $1/4$ の確率で $0,1,2,3$ になります。 よって、$X$ を $1,2,3$ にするのに必要な操作回数の期待値はいずれも $4$ です。

入力例 2

2
1 2 1 2

出力例 2

0
499122180
4
499122180

$X$ を $0,1,2,3$ にするのに必要な操作回数の期待値は、それぞれ $0,7/2,4,7/2$ です。

入力例 3

4
337 780 799 10 796 875 331 223 941 67 148 483 390 565 116 355

出力例 3

0
468683018
635850749
96019779
657074071
24757563
745107950
665159588
551278361
143136064
557841197
185790407
988018173
247117461
129098626
789682908