至少一个

题目描述

给你一个整数 $M$ 和 $N$ 对整数 $(A_1, B_1), (A_2, B_2), \dots, (A_N, B_N)$。

对所有 $i$,都有 $1 \le A_i \lt B_i \le M$。

当序列 $S$ 满足以下条件时,称其为「好序列」:

• $S$ 是序列 $(1,2,3,\dots,M)$ 的连续子序列。
• 对所有 $i$,$S$ 中包含 $A_i$ 和 $B_i$ 中的至少一个。

设 $f(k)$ 为长度为 $k$ 的好序列的个数。

请枚举 $f(1), f(2), \dots, f(M)$。

输入格式

输入按以下格式从标准输入给出:

N M
A_1 B_1
A_2 B_2
⋮
A_N B_N

输出格式

按以下格式输出答案:

f(1) f(2) … f(M)

样例

3 5
1 3
1 4
2 5

0 1 3 2 1

所有好序列的列表如下。

$(1,2)$

$(1,2,3)$

$(2,3,4)$

$(3,4,5)$

$(1,2,3,4)$

$(2,3,4,5)$

$(1,2,3,4,5)$

1 2
1 2

2 1

5 9
1 5
1 7
5 6
5 8
2 6

0 0 1 2 4 4 3 2 1

数据范围

• $1 \le N \le 2 \times 10^5$
• $2 \le M \le 2 \times 10^5$
• $1 \le A_i \lt B_i \le M$
• 输入中的所有值均为整数。