在藏蓝铁路的碧水湖大桥落成之际，一群铁路工程蚤聚在一起，庆祝这一伟大的建筑工程。

在修建过程中，有一些多余的铁轨。为了环保（省钱），废弃的铁轨会被存到仓库等待下次利用。

有 $N$ 个路段，每个路段有一个废弃铁轨专属仓库。其中，第 $i$ 个路段余下的铁轨长度为 $A_i$ km，而该路段的专属仓库最多能存 $B_i$ km。

工程蚤们会按照 $i=1\sim n-1$ 的顺序进行操作，来将废弃的铁轨进行集中：

• 关闭第 $i$ 个路段的仓库；
• 从 $[i+1,n]$ 中随机选择一个整数 $j$，把第 $i$ 个路段的仓库中的铁轨全部放到第 $j$ 个路段的仓库中；
• 如果超出容量，则弃置多出的部分（也就是 $A_j\leftarrow min(A_i+A_j,B_j)$）。

现在，对于每个 $i\in [0,B_n]$，问第 $n$ 个路段的仓库最终有 $i$ km 铁轨的概率。你只需要输出答案模 $998244353$ 后的值即可。

输入格式

第一行一个正整数，表示 $n$。

接下来 $n$ 行，每行两个非负整数，表示 $A_i$ 和 $B_i$。

输出格式

一行 $B_n+1$ 个整数，分别表示 $i=0,i=1,...,i=B_n$ 的答案模 $998244353$ 后的值。可以证明答案一定可以被表示为 $\frac{a}{b}$ 的形式，其中 $gcd(a,b)=1$，你需要输出整数 $c$ 满足 $bc\equiv amod998244353$。

样例一

input

3
1 2
1 1
0 3

output

0 499122177 499122177 0

样例二

input

8
1 3
1 2
0 1
0 2
1 6
0 1
3 3
0 10

output

0 0 0 748683265 376718405 301057821 570029216 0 0 0 0

样例三/四/五/六

见下发文件。

限制与约定

对于 $100\mathrm{\%}$ 的数据，$1\le n\le 50,0\le A_i\le B_i\le 30$。

时间限制：$\mathtt{\text{5s}}$

空间限制：$\mathtt{\text{512MB}}$