Problem Statement

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$.

Constraints

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

Input

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}

Output

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.