초대

Iris는 2022 ICPC 타오위안 지역 대회 주최 측에서 일한다. COVID-19 때문에 대만의 ICPC 지역 대회는 지난 몇 년 동안 개회식에 지도자를 초청하지 못했다. 2022 ICPC 타오위안 지역 대회 주최 측은 타오위안 시의 지도자들을 개회식에 초청하고 싶어 한다.

타오위안 시에는 1번부터 $n$번까지 번호가 매겨진 지도자 $n$명이 있다. Iris의 임무는 이 지도자들 중 몇 명을 개회식에 초청하는 것이다. $i$번 지도자는 시간대 $\ell_i$부터 $r_i$까지 참석할 수 있다. Iris가 지도자 $k$명 $a_1, a_2, \dots, a_k$를 초청하려면, 이들 모두에게 공통으로 참석 가능한 시간대가 있어야 한다. 즉 모든 $1 \le i \le k$에 대해 $\ell_{a_i} \le x \le r_{a_i}$를 만족하는 시간대 $x$가 존재해야 한다.

Iris는 같은 시간대에 함께 참석할 수 있는 지도자 $k$명의 조합이 몇 가지인지 알고 싶어 한다. $1$부터 $n$까지 모든 $k$에 대해 답을 구하라. 조합의 수가 매우 많을 수 있으므로 $998244353$으로 나눈 나머지를 출력한다.

첫 줄에 지도자의 수 $n$이 주어진다. 이어지는 $n$개의 줄 중 $i$번째 줄에는 두 수 $\ell_i$와 $r_i$가 주어지며, 이는 $i$번 지도자가 시간대 $\ell_i$부터 $r_i$까지 참석할 수 있다는 뜻이다.

$n$개의 수를 출력한다. $k$번째 수는 공통으로 참석 가능한 시간대가 있는 지도자 $k$명의 조합 수이다. 답은 $998244353$으로 나눈 나머지로 출력한다.

• $1 \le n \le 100000$
• $0 \le \ell_i \le r_i \le 1000000000$ ($1 \le i \le n$)