半生不熟的煎饼

题目描述

你决定烤 $N$ 个煎饼并把它们叠成一摞。

第 $i$ 个煎饼烤好后，它的大小会以 $\frac{1}{2}$ 的概率变成 $A_i$，以 $\frac{1}{2}$ 的概率变成 $B_i$。各个煎饼之间相互独立。

烤好全部 $N$ 个煎饼后，你把它们按大小从小到大从上往下叠成一摞。

设 $f(k)$ 为从上往下数第 $k$ 个煎饼大小的期望值。可以证明 $f(k)\times 2^N$ 是整数。

对每个 $k=1,2,\dots,N$，求 $\left(f(k)\times 2^N\right)\bmod 998244353$。

输入格式

第一行一个整数 $N$。

接下来 $N$ 行，第 $i$ 行两个整数 $A_i, B_i$。

输出格式

输出 $N$ 行。第 $k$ 行表示 $k$ 对应的答案。

3
1000 3000
5000 8000
2000 9000

14000
36000
62000

样例 1 解释

共有 $2^3=8$ 种等概率情况。例如三个煎饼都取 $A_i$ 时，大小依次为 $1000,5000,2000$，排序后为 $1000,2000,5000$，对答案的贡献为这三个数之和 $8000$。把 $8$ 种情况下排序后的第 $k$ 个数全部相加，就得到 $f(k)\times 2^N$。

5
1 2
2 4
2 6
2 8
2 10

48
68
92
156
260

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

276177791
934318446
44503192
525981255
598596982
938987475
225190244
12980826
379197102
651032077
502004535
311899162
754356358
457449763
807861939
196627040

数据范围

对于所有测试数据，保证 $1\le N\le 120000$，$1\le A_i<B_i<998244353$。

子任务

本题共 20 个测试点，按测试点计分：

每个测试点单独评分，全部测试点的得分之和即为本题得分。