AT_abc463_f.Senshuraku

A tournament is being held with $2N$ players. From now on, each player will play exactly one match. In the remaining $N$ matches, the $i$-th $(1\le i\le N)$ match is played between the $(2i-1)$-th and $2i$-th players.

In each match, one of the two competing players wins and the other loses. Which player wins is determined independently for each match, and each player wins with probability $\dfrac12$.

Before the last $N$ matches begin, the $i$-th $(1\le i\le2N)$ player has won $A _ i$ times. After all matches are over, the champion is chosen from among the players with the most wins, uniformly at random and independently of the previous match results.

For each of the first, second, $\ldots$, $2N$-th players, find the probability, modulo $998244353$, of that player becoming the champion.

Definition of probability modulo $998244353$

It can be proved that the sought probability is always a rational number. Moreover, under the constraints of this problem, it can be proved that when the rational number is expressed as an irreducible fraction $\frac{P}{Q}$, we have $Q {{}\not\equiv{}} 0 \pmod{998244353}$. Therefore, there is a unique integer $R$ satisfying $R \times Q \equiv P \pmod{998244353}, 0 \leq R \lt 998244353$. Find this $R$.

现正举行一场有 $2N$ 名选手参加的比赛。从现在起，每名选手恰好进行一场比赛。在接下来的 $N$ 场比赛中，第 $i$ 场 $(1\le i\le N)$ 比赛由第 $(2i-1)$ 号选手与第 $2i$ 号选手对战。

在每场比赛中，两名参赛选手中有一人获胜、另一人落败。哪位选手获胜是相互独立决定的，且每位选手获胜的概率均为 $\dfrac{1}{2}$。

在最后这 $N$ 场比赛开始前，第 $i$ 号 $(1\le i\le 2N)$ 选手已获胜 $A_i$ 次。所有比赛结束后，冠军将从所有获胜次数最多的选手中均匀随机选出（即若有多名选手并列最多胜场，则从中等概率随机选择一人），且该选择独立于之前所有比赛的结果。

对第 $1$、第 $2$、……、第 $2N$ 号选手中的每一位，请分别求出其成为冠军的概率，并对 $998244353$ 取模。

概率对 $998244353$ 取模的定义

可以证明：所求概率恒为有理数。此外，在本题约束条件下，可进一步证明：当该有理数表示为既约分数 $\frac{P}{Q}$ 时，恒有 $Q \not\equiv 0 \pmod{998244353}$。因此，存在唯一整数 $R$ 满足

$$R \times Q \equiv P \pmod{998244353}, \quad 0 \leq R < 998244353.$$

请输出该 $R$ 值。

The input is given from Standard Input in the following format:

$N$
$A _ 1$ $A _ 2$
$A _ 3$ $A _ 4$
$\vdots$
$A _ {2N-1}$ $A _ {2N}$

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

$N$
$A _ 1$ $A _ 2$
$A _ 3$ $A _ 4$
$\vdots$
$A _ {2N-1}$ $A _ {2N}$

Output the probability of the first player becoming the champion, the probability of the second player becoming the champion, $\ldots$, the probability of the $2N$-th player becoming the champion, in this order, separated by spaces, on a single line.

输出第一名选手成为冠军的概率、第二名选手成为冠军的概率、……、第 $2N$ 名选手成为冠军的概率，按此顺序，以空格分隔，输出在一行中。

Sample 1 Explanation:
For example, the third player becomes the champion in the following cases:

• If the third player wins in the second match, the fifth player wins in the third match, and the seventh player wins in the fourth match, the third player becomes the champion with probability $\dfrac13$.
• If the third player wins in the second match, the sixth player wins in the third match, and the seventh player wins in the fourth match, the third player becomes the champion with probability $\dfrac14$.

Thus, the probability of the third player becoming the champion is $\dfrac18\times\dfrac13+\dfrac18\times\dfrac14=\dfrac7{96}$. We have $259959467\times96\equiv7\pmod{998244353}$, so the probability of the third player becoming the champion in modulo-$998244353$ expression is $259959467$.

The probability of each player becoming the champion is $0,0,\dfrac7{96},\dfrac{43}{96},0,\dfrac3{96},0,\dfrac{43}{96}$. Thus, output 0 0 259959467 883862188 0 967049217 0 883862188.

Sample 2 Explanation:
It is possible that no one has won yet.

By symmetry, each player becomes the champion with probability $\dfrac1{12}$.

Constraints

• $1\le N\le2\times10 ^ 5$
• $0\le A _ i\lt2N\ (1\le i\le 2N)$
• All input values are integers.

样例 1 解释：
例如，第三位选手在以下情形中成为冠军：

• 若第三位选手赢得第二场比赛，第五位选手赢得第三场比赛，第七位选手赢得第四场比赛，则第三位选手以概率 $\dfrac13$ 成为冠军。
• 若第三位选手赢得第二场比赛，第六位选手赢得第三场比赛，第七位选手赢得第四场比赛，则第三位选手以概率 $\dfrac14$ 成为冠军。

因此，第三位选手成为冠军的概率为 $\dfrac18\times\dfrac13+\dfrac18\times\dfrac14=\dfrac7{96}$。我们有 $259959467\times96\equiv7\pmod{998244353}$，故第三位选手成为冠军的概率在模 $998244353$ 意义下的表示为 $259959467$。

每位选手成为冠军的概率依次为 $0,0,\dfrac7{96},\dfrac{43}{96},0,\dfrac3{96},0,\dfrac{43}{96}$。因此输出 0 0 259959467 883862188 0 967049217 0 883862188。

样例 2 解释：
有可能尚无任何人获胜。

由对称性可知，每位选手成为冠军的概率均为 $\dfrac1{12}$。

约束条件

• $1\le N\le2\times10 ^ 5$
• $0\le A _ i\lt2N\ (1\le i\le 2N)$
• 所有输入值均为整数。