AT_abc463_f [ABC463F] 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 $ .

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

### Sample Explanation 1 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 Explanation 2 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.