410245: GYM103990 I Invitation

Iris works for the host of the 2022 ICPC Taoyuan Regional Contest. Due to COVID-19, the ICPC regional contests in Taiwan could not invite any leader to the opening ceremony in the past few years. The host of the 2022 ICPC Taoyuan Regional Contest is eager to invite leaders in Taoyuan City to attend the opening ceremony.

There are $$$n$$$ leaders numbered from $$$1$$$ to $$$n$$$ in Taoyuan City, and Iris's task is to invite some leaders to attend the ceremony. Leader $$$i$$$ is available from time slot $$$\ell_i$$$ to time slot $$$r_i$$$. If Iris wants to invite $$$k$$$ leaders $$$a_1,a_2,...a_k$$$, then all of them must have a common available time slot. It means that Iris has to find a time slot $$$x$$$ such that $$$\ell_{a_i} \leq x \leq r_{a_i}$$$ for $$$1 \leq i \leq k$$$.

Iris is curious about the number of combinations of $$$k$$$ leaders available at the same time? You need to give the answers for all $$$k$$$ between $$$1$$$ and $$$n$$$. The combinations may be extremely numerous, please output the number of combinations modulo $$$998244353$$$.

The first line of input contains one integer $$$n$$$, the number of leaders. The following $$$n$$$ lines indicate the leaders' available time slots. The $$$i$$$-th line of these $$$n$$$ lines contains two numbers $$$\ell_i$$$ and $$$r_i$$$. The $$$i$$$-th leader is available at time $$$\ell_i$$$ to $$$r_i$$$.

• $$$1\leq n \le 100000$$$
• $$$0\leq \ell_i \le r_i \le 1000000000$$$ for $$$1\le i \le n$$$.

Print $$$n$$$ numbers. The $$$k$$$-th number is the number of combinations of $$$k$$$ leaders having a common available time slot. Please modulo the answer with $$$998244353$$$.

3
1 2
2 3
3 4

3 2 0