题目描述

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

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

有 $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,1,\ldots,B_n$ 的答案模 998244353 后的值。

可以证明答案一定可以被表示为 $\frac{a}{b}$ 的形式，其中 $\gcd(a,b)=1$，你需要输出整数 $c$ 满足

$bc\equiv a\pmod{998244353}$。

样例 1

输入

3
1 2
1 1
0 3

输出

0 499122177 499122177 0

样例 2

输入

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

输出

0 0 0 748683265 376718405 301057821 570029216 0 0 0 0

限制与约定

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