시간 제한메모리 제한제출정답맞힌 사람정답 비율
3 초 (추가 시간 없음) 1024 MB30161661.538%

문제

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 $ℓ_i$ to time slot $r_i$. If Iris wants to invite $k$ leaders $a_1, a_2, \dots ,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 $ℓ_{a_i} ≤ x ≤ r_{a_i}$ for $1 ≤ i ≤ 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 $ℓ_i$ and $r_i$. The $i$-th leader is available at time $ℓ_i$ to $r_i$.

출력

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$.

제한

  • $1 ≤ n ≤ 100000$
  • $0 ≤ ℓ_i ≤ r_i ≤ 1000000000$ for $1 ≤ i ≤ n$.

예제 입력 1

3
1 2
2 3
3 4

예제 출력 1

3 2 0