分数: 7 点
注意
这个问题有非常严格的内存限制。
问题陈述
给你一个整数 M 和 N 整数对 (L_1, R_1), \dots, (L_N, R_N).对于每个 i (1 \leq i \leq N),它认为 1 \leq L_i \leq R_i \leq M.
对于每个 K = 1, 2, \dots, M,解决以下问题:
有 2^N 可能的子集 S \subseteq \lbrace 1,2,\dots,N\rbrace。其中,满足以下条件的有多少?输出答案取模 998244353.
- 整数个数 m (1 \leq m \leq M) 满足以下条件正好是 K:
- 存在一个整数 i \in S 这样 L_i \leq m \leq R_i.
约束
- 1 \leq N \leq 2000
- 1 \leq M \leq 4000
- 1 \leq L_i \leq R_i \leq M
- 所有输入值均为整数
输入
输入由标准输入给出,格式如下:
N M L_1 R_1 L_2 R_2 \vdots L_N R_N
输出
打印 M 行。上 i第行,输出答案 K = i.
示例输入 1
3 4 1 2 3 4 2 4
示例输出 1
0 2 2 3
当 K=1,有 0 子集 S 满足条件。
当 K=2,有 2 这样的子集: \lbrace 1\rbrace , \lbrace 2\rbrace.
当 K=3,有 2 这样的子集: \lbrace 3\rbrace , \lbrace 2,3\rbrace.
当 K=4,有 3 这样的子集: \lbrace 1,2\rbrace , \lbrace 1,3\rbrace , \lbrace 1,2,3\rbrace.
示例输入 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