题目描述

すぬけ君得到了一个随机数生成器。这个随机数生成器会生成 $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$ 所需操作次数的期望值。期望值需要对 $998244353$ 取模输出。更准确地说，若期望值为既约分数 $P/Q$，则输出满足 $R\times Q\equiv P\pmod{998244353},\ 0\leq R<998244353$ 的唯一整数 $R$。

另外，题目的约束保证了对于所有 $i$，将 $X$ 变为 $i$ 所需操作次数的期望值作为有理数是存在的，并且其模 $998244353$ 的整数表示也是有定义的。

输入格式

输入以如下格式从标准输入读入。

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

输出格式

输出 $2^N$ 行。第 $i+1$ 行（$0\leq i\leq 2^N-1$）输出将 $X$ 变为 $i$ 所需操作次数的期望值对 $998244353$ 取模后的结果。

样例 1

输入

2
1 1 1 1

输出

0
4
4
4

样例 2

输入

2
1 2 1 2

输出

0
499122180
4
499122180

样例 3

输入

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

输出

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

说明/提示

限制条件

• $1\leq N\leq 18$
• $1\leq A_i\leq 1000$
• 输入的所有值均为整数。

样例解释 1

操作 $0$ 次时 $X=0$，所以将 $X$ 变为 $0$ 所需操作次数的期望值为 $0$。另外，无论从哪个状态操作，操作后 $X$ 的值都以 $1/4$ 的概率变为 $0,1,2,3$。因此，将 $X$ 变为 $1,2,3$ 所需操作次数的期望值均为 $4$。

样例解释 2

将 $X$ 变为 $0,1,2,3$ 所需操作次数的期望值分别为 $0,7/2,4,7/2$。

由 ChatGPT 4.1 翻译