时空限制

1S/512M

题目描述

一场盛大的锦标赛正在举行，共有 $2^n$ 位选手参与，选手编号从 $1$ 到 $2^n$。每位选手 $i$ 都有一个能力值 $a_i$。

比赛采用单败淘汰制，共进行 $n$ 轮。赛程是固定的：

1. 初始轮 (第一轮)：选手按编号顺序配对，即 ($1$ vs $2$), ($3$ vs $4$), ..., ($2^n-1$ vs $2^n$)。
2. 后续轮次：每一轮中，前一轮的胜者们将保持他们原来的相对顺序，再次按顺序配对比赛。例如，$(1,2)$ 号比赛的胜者，将在下一轮对阵 $(3,4)$ 号比赛的胜者。以此类推。

当两位选手 $i$ 和 $j$ 对战时，选手 $i$ 的获胜概率为 $\frac{a_i}{a_i + a_j}$，选手 $j$ 的获胜概率则为 $\frac{a_j}{a_i + a_j}$。

你的任务是计算每位选手最终赢得锦标赛冠军的概率。你需要将结果对 $998244353$ 取模。

由于答案可能是一个分数，设 $P = 998244353$，一个最简分数 $\frac{p}{q}$ 应输出 $p \times q^{P-2} \bmod{P}$。

格式

输入格式

第一行包含一个整数 $n$。

第二行包含 $2^n$ 个整数，表示 $a_1, a_2, \dots, a_{2^n}$。第 $i$ 个数表示第 $i$ 个人的能力值。

输出格式

输出一行，$2^n$ 个整数，用空格隔开。第 $i$ 个整数表示第 $i$ 位选手赢得冠军的概率对 $998244353$ 取模后的结果。

样例

样例输入 #1

1
10 20

样例输出 #1

332748118 665496236

样例解释 #1

有 $2^1=2$ 位选手，能力值分别为 $10$ 和 $20$。 只有一轮比赛，选手 $1$ 和选手 $2$ 对战。 选手 $1$ 获胜（即成为冠军）的概率是 $\frac{10}{10+20} = \frac{1}{3}$。 选手 $2$ 获胜（即成为冠军）的概率是 $\frac{20}{10+20} = \frac{2}{3}$。

将这两个概率对 $998244353$ 取模：

• 对于 $\frac{1}{3}$，需要计算 $1 \cdot 3^{998244353-2} \pmod{998244353}$，结果为 $332748118$。
• 对于 $\frac{2}{3}$，需要计算 $2 \cdot 3^{998244353-2} \pmod{998244353}$，结果为 $665496236$。

样例输入 #2

2
4 6 3 9

样例输出 #2

96533520 239578645 705901364 954475178

数据规模

对于 $20 \%$ 的数据， $1 \leq n \leq 3$。

对于 $100\%$ 的数据，满足 $1 \le n \le 12$，$1 \le a_i \le 10^6$。