AT_abc463_f [ABC463F] Senshuraku

$ 2N $ 人の選手が参加する大会が行われています。 これから、それぞれの選手は $ 1 $ 回試合を行います。 残る $ N $ 回の試合のうち、 $ i $ 番目 $ (1\le i\le N) $ の試合では $ 2i-1 $ 番目の選手と $ 2i $ 番目の選手が対戦を行います。 それぞれの試合では、対戦する $ 2 $ 人の選手のうち $ 1 $ 人が勝ち、もう $ 1 $ 人が負けます。 どちらの選手が勝つかは試合ごとに独立に確率 $ \dfrac12 $ で決まります。 最後の $ N $ 試合が始まる前、 $ i $ 番目 $ (1\le i\le2N) $ の選手は $ A _ i $ 回勝っています。 すべての試合が終わったあと、勝った回数が最も多い選手の中から一様ランダムかつこれまでの試合結果と独立に優勝選手が選ばれます。 $ 1 $ 番目の選手、 $ 2 $ 番目の選手、 $ \ldots $ 、 $ 2N $ 番目の選手のそれぞれについて、優勝する確率を $ {}\bmod998244353 $ で求めてください。 確率 $ {}\bmod{998244353} $ の定義 求める確率は必ず有理数になることが証明できます。 また、この問題の制約のもとでは、求める有理数を既約分数 $ \frac{P}{Q} $ で表した時、 $ Q {{}\not\equiv{}} 0 \pmod{998244353} $ となることが証明できます。 よって、 $ R \times Q \equiv P \pmod{998244353}, 0 \leq R \lt 998244353 $ を満たす整数 $ R $ が一意に定まります。 この $ R $ を答えてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ A _ 1 $ $ A _ 2 $ $ A _ 3 $ $ A _ 4 $ $ \vdots $ $ A _ {2N-1} $ $ A _ {2N} $

$ 1 $ 番目の選手が優勝する確率、 $ 2 $ 番目の選手が優勝する確率、 $ \ldots $ 、 $ 2N $ 番目の選手が優勝する確率を、この順に空白を区切りとして $ 1 $ 行に出力せよ。

### Sample Explanation 1 例えば、 $ 3 $ 番目の選手が優勝するのは次のような場合です。 - $ 2 $ 番目の試合で自分が勝ち、 $ 3 $ 番目の試合で $ 5 $ 番目の選手が勝ち、 $ 4 $ 番目の試合で $ 7 $ 番目の選手が勝った場合、 $ \dfrac13 $ の確率で優勝する。 - $ 2 $ 番目の試合で自分が勝ち、 $ 3 $ 番目の試合で $ 6 $ 番目の選手が勝ち、 $ 4 $ 番目の試合で $ 7 $ 番目の選手が勝った場合、 $ \dfrac14 $ の確率で優勝する。 よって、 $ 3 $ 番目の選手が優勝する確率は $ \dfrac18\times\dfrac13+\dfrac18\times\dfrac14=\dfrac7{96} $ です。 $ 259959467\times96\equiv7\pmod{998244353} $ なので、 $ 3 $ 番目の選手が優勝する確率は $ {}\bmod998244353 $ で $ 259959467 $ です。 それぞれの選手が優勝する確率は $ 0,0,\dfrac7{96},\dfrac{43}{96},0,\dfrac3{96},0,\dfrac{43}{96} $ です。 よって、`0 0 259959467 883862188 0 967049217 0 883862188` を出力してください。 ### Sample Explanation 2 これまで誰も勝利していない場合もあります。 対称性より、どの選手が優勝する確率も $ \dfrac1{12} $ です。 ### Constraints - $ 1\le N\le2\times10 ^ 5 $ - $ 0\le A _ i\lt2N\ (1\le i\le 2N) $ - 入力はすべて整数