Q - 区間の和集合 解説 /

実行時間制限: 10 sec / メモリ制限: 16 MiB

配点 : 7 点

注意

この問題はメモリ制限が非常に厳しいです。

問題文

整数 M および N 個の整数の組 (L_1, R_1), \dots, (L_N, R_N) が与えられます。ここで任意の 1 \leq i \leq N を満たす整数 i について 1 \leq L_i \leq R_i \leq M が成り立ちます。
K = 1, 2, \dots, M に対して以下の問題の答えを求めてください。

S \subseteq \lbrace 1, 2,\dots, N \rbrace である集合 S としてあり得るものは 2^N 通りありますが、そのうち以下の条件を満たすものは何個ありますか？答えを 998244353 で割った余りを求めてください。

  • 1 以上 M 以下の整数 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 の時、条件を満たす S は 0 個です。
K=2 の時、条件を満たす S は \lbrace 1 \rbrace, \lbrace 2 \rbrace の 2 個です。
K=3 の時、条件を満たす S は \lbrace 3 \rbrace, \lbrace 2,3 \rbrace の 2 個です。
K=4 の時、条件を満たす S は \lbrace 1,2 \rbrace, \lbrace 1,3 \rbrace, \lbrace 1,2,3 \rbrace の 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

Score : 7 points

Note

This problem has a very strict memory limit.

Problem Statement

You are given an integer M and N pairs of integers (L_1, R_1), \dots, (L_N, R_N). For each i (1 \leq i \leq N), it holds that 1 \leq L_i \leq R_i \leq M.

For each K = 1, 2, \dots, M, solve the following problem:

There are 2^N possible subsets S \subseteq \lbrace 1,2,\dots,N\rbrace. Among them, how many satisfy the following condition? Output the answer modulo 998244353.

  • The number of integers m (1 \leq m \leq M) satisfying the following condition is exactly K:
    • There exists an integer i \in S such that L_i \leq m \leq R_i.

Constraints

  • 1 \leq N \leq 2000
  • 1 \leq M \leq 4000
  • 1 \leq L_i \leq R_i \leq M
  • All input values are integers

Input

The input is given from standard input in the following format:

N M
L_1 R_1
L_2 R_2
\vdots
L_N R_N

Output

Print M lines. On the i-th line, output the answer for K = i.

Sample Input 1

3 4
1 2
3 4
2 4

Sample Output 1

0
2
2
3

When K=1, there are 0 subsets S that satisfy the condition.
When K=2, there are 2 such subsets: \lbrace 1\rbrace , \lbrace 2\rbrace.
When K=3, there are 2 such subsets: \lbrace 3\rbrace , \lbrace 2,3\rbrace.
When K=4, there are 3 such subsets: \lbrace 1,2\rbrace , \lbrace 1,3\rbrace , \lbrace 1,2,3\rbrace.

Sample Input 2

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

Sample Output 2

0
0
3
2
15
25
26
20
72
92