/ 
実行時間制限: 4 sec / メモリ制限: 1024 MiB
配点 : 600 点
問題文
あなたは N 個のパンケーキを焼き、1 個の山に積み上げることにしました。
i 番目のパンケーキを焼いたときの大きさは、確率 1/2 で A_i に、確率 1/2 で B_i になります。 この事象はパンケーキごとに独立です。
N 個のパンケーキを焼き終えた後、上から大きさが昇順になるように 1 個の山に積み上げます。
上から k 番目に積まれるパンケーキの大きさの期待値を f(k) とします。 このとき、f(k) \times 2^N は整数になることが証明できます。
k=1,\dots,N について、\left( f(k) \times 2^N \right) \bmod 998244353 の値を求めてください。
制約
- 1 \leq N \leq 120\,000
- 1 \leq A_i < B_i < 998244353
- 入力される値はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N A_1 B_1 \vdots A_N B_N
出力
N 行出力せよ。l 行目 (1 \leq l \leq N) には、k=l の場合の答えを出力せよ。
入力例 1
3 1000 3000 5000 8000 2000 9000
出力例 1
14000 36000 62000
積み上げたパンケーキの大きさを上から並べた数列は、1/8 ずつの確率で以下の 8 通りのいずれかになります。
- (1000,\ 2000,\ 5000)
- (1000,\ 5000,\ 9000)
- (1000,\ 2000,\ 8000)
- (1000,\ 8000,\ 9000)
- (2000,\ 3000,\ 5000)
- (3000,\ 5000,\ 9000)
- (2000,\ 3000,\ 8000)
- (3000,\ 8000,\ 9000)
このとき、f(1), f(2), f(3) の値は以下のようになります。
- \displaystyle f(1) = \frac{1000+1000+1000+1000+2000+3000+2000+3000}{8} = 1750
- \displaystyle f(2) = \frac{2000+5000+2000+8000+3000+5000+3000+8000}{8} = 4500
- \displaystyle f(3) = \frac{5000+9000+8000+9000+5000+9000+8000+9000}{8} = 7750
入力例 2
5 1 2 2 4 2 6 2 8 2 10
出力例 2
48 68 92 156 260
入力例 3
16 590750810 881929947 587037424 967895551 443510128 787944380 689922795 844014120 384247532 471383266 66520009 905781395 927671784 951066952 233378255 857611956 91689637 419605608 280270213 778410686 141205183 456501569 59232352 956004175 150307063 296071558 84333651 869834323 269686721 755659326 152999727 215448458
出力例 3
276177791 934318446 44503192 525981255 598596982 938987475 225190244 12980826 379197102 651032077 502004535 311899162 754356358 457449763 807861939 196627040
Score : 600 points
Problem Statement
You have decided to bake N pancakes and stack them into one pile.
When the i-th pancake is baked, its size becomes A_i with probability 1/2 and B_i with probability 1/2. These events are independent across pancakes.
After baking all N pancakes, you stack them into one pile so that their sizes are in ascending order from the top.
Let f(k) be the expected value of the size of the k-th pancake from the top. It can be proved that f(k) \times 2^N is an integer.
For k=1,\dots,N, find the value of \left( f(k) \times 2^N \right) \bmod 998244353.
Constraints
- 1 \leq N \leq 120\,000
- 1 \leq A_i < B_i < 998244353
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N A_1 B_1 \vdots A_N B_N
Output
Print N lines. The l-th line (1 \leq l \leq N) should contain the answer for k=l.
Sample Input 1
3 1000 3000 5000 8000 2000 9000
Sample Output 1
14000 36000 62000
The sequence of sizes of the stacked pancakes from the top is one of the following 8 sequences, each with probability 1/8.
- (1000,\ 2000,\ 5000)
- (1000,\ 5000,\ 9000)
- (1000,\ 2000,\ 8000)
- (1000,\ 8000,\ 9000)
- (2000,\ 3000,\ 5000)
- (3000,\ 5000,\ 9000)
- (2000,\ 3000,\ 8000)
- (3000,\ 8000,\ 9000)
Here, the values of f(1), f(2), f(3) are as follows.
- \displaystyle f(1) = \frac{1000+1000+1000+1000+2000+3000+2000+3000}{8} = 1750
- \displaystyle f(2) = \frac{2000+5000+2000+8000+3000+5000+3000+8000}{8} = 4500
- \displaystyle f(3) = \frac{5000+9000+8000+9000+5000+9000+8000+9000}{8} = 7750
Sample Input 2
5 1 2 2 4 2 6 2 8 2 10
Sample Output 2
48 68 92 156 260
Sample Input 3
16 590750810 881929947 587037424 967895551 443510128 787944380 689922795 844014120 384247532 471383266 66520009 905781395 927671784 951066952 233378255 857611956 91689637 419605608 280270213 778410686 141205183 456501569 59232352 956004175 150307063 296071558 84333651 869834323 269686721 755659326 152999727 215448458
Sample Output 3
276177791 934318446 44503192 525981255 598596982 938987475 225190244 12980826 379197102 651032077 502004535 311899162 754356358 457449763 807861939 196627040