Iris 在 2022 年 ICPC 桃园区域赛的主办方工作。由于 COVID-19 的影响，过去几年台湾的 ICPC 区域赛无法邀请任何领导参加开幕式。2022 年 ICPC 桃园区域赛的主办方非常渴望邀请桃园市的领导们参加开幕式。

桃园市共有 $n$ 位领导，编号从 $1$ 到 $n$，Iris 的任务是邀请一些领导参加开幕式。第 $i$ 位领导的空闲时间段为 $\ell_i$ 到 $r_i$。如果 Iris 想要邀请 $k$ 位领导 $a_1, a_2, \dots, a_k$，那么他们必须拥有一个共同的空闲时间段。这意味着 Iris 必须找到一个时间点 $x$，使得对于所有 $1 \le i \le k$，满足 $\ell_{a_i} \le x \le r_{a_i}$。

Iris 对有多少种 $k$ 位领导的组合可以在同一时间参加感到好奇。你需要给出对于所有 $1$ 到 $n$ 之间的 $k$ 的答案。组合数量可能非常巨大，请输出对 $998244353$ 取模后的结果。

输入格式

输入的第一行包含一个整数 $n$，表示领导的人数。接下来的 $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$。

样例

样例输入 1

3
1 2
2 3
3 4

样例输出 1

3 2 0