注意

本题的内存限制非常严格。

题目描述

给定整数 $M$ 和 $N$ 个闭区间

其中 $1\le L_i\le R_i\le M$。

对于每个 $K=1,2,\ldots,M$，回答以下问题：

从集合 $\{1,2,\ldots,N\}$ 的 $2^N$ 个子集 $S$ 中，选出满足下述条件的子集，其数量是多少？答案对 $998244353$ 取模。

• 在 $1$ 到 $M$ 的整数中，恰好有 $K$ 个整数 $m$ 被 $S$ 中至少一个区间覆盖。也就是说，恰好有 $K$ 个 $m$ 满足：存在 $i\in S$，使得 $L_i\le m\le R_i$。

限制条件

• $1\le N\le 2000$
• $1\le M\le 4000$
• $1\le L_i\le R_i\le M$
• 所有输入均为整数。

输入

N M
L_1 R_1
L_2 R_2
...
L_N R_N

输出

输出 $M$ 行。第 $i$ 行输出 $K=i$ 时的答案。

样例输入 1

3 4
1 2
3 4
2 4

样例输出 1

0
2
2
3

• $K=1$ 时，没有满足条件的子集；
• $K=2$ 时，满足条件的子集为 $\{1\},\{2\}$；
• $K=3$ 时，满足条件的子集为 $\{3\},\{2,3\}$；
• $K=4$ 时，满足条件的子集为 $\{1,2\},\{1,3\},\{1,2,3\}$。

样例输入 2

8 10
6 10
1 4
5 9
6 8
1 5
7 9
4 6
4 8

样例输出 2

0
0
3
2
15
25
26
20
72
92