题目描述

Snuke 发现了一个随机数生成器。它可以生成一个介于 $0$ 和 $2^N-1$（包含）之间的整数。一个整数序列 $A_0, A_1, ..., A_{2^N-1}$ 表示每个这些整数被生成的概率。整数 $i$ （$0 \leq i \leq 2^N-1$）以 $A_i / S$ 的概率被生成，其中 $S = \sum_{i=0}^{2^N-1} A_i$。每次执行生成器时，生成整数的过程是相互独立的。

Snuke 有一个整数 $X$，初始为 $0$。他可以执行以下操作任意次数：

• 使用生成器生成一个整数 $v$，并用 $X \oplus v$ 替换 $X$，其中 $\oplus$ 表示按位异或。

对于每个整数 $i$ （$0 \leq i \leq 2^N-1$），找到 $X$ 变为 $i$ 的预期操作次数，并以 $998244353$ 取模后输出。更正式地说，将预期操作次数表示为一个既约分数 $P/Q$。那么，存在唯一的整数 $R$，使得 $R \times Q \equiv P \mod 998244353$，且 $0 \leq R < 998244353$，所以输出这个 $R$。

我们可以证明，对于每个 $i$，$X$ 变为 $i$ 的预期操作次数是一个有限的有理数，并且其按 $998244353$ 取模后的整数表示是可以确定的。

约束条件

• $1 \leq N \leq 18$
• $1 \leq A_i \leq 1000$
• 输入中的所有值都是整数。

输入

输入以以下格式从标准输入给出：

$N$ $A_0$ $A_1$ $...$ $A_{2^N-1}$

输出

输出 $2^N$ 行。第 $(i+1)$ 行（$0 \leq i \leq 2^N-1$）应包含 $X$ 变为 $i$ 的预期操作次数，按 $998244353$ 取模后的结果。

示例输入1

2
1 1 1 1

示例输出1

0
4
4
4

$X=0$ 时不需要进行任何操作，因此 $X$ 变为 $0$ 的预期操作次数为 $0$。

此外，从任何状态开始，经过一次操作后，$X$ 的值可能是 $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