当前没有测试数据。

E - 至少一个

得分 : $500$ 分

问题描述

给定整数 $M$ 和 $N$ 对整数 $(A_1, B_1), (A_2, B_2), \dots, (A_N, B_N)$。
对于所有的 $i$，满足 $1 \leq A_i \lt B_i \leq M$。

一个序列 $S$ 被称为好序列，如果满足以下条件：

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

记 $f(k)$ 为长度为 $k$ 的可能的好序列个数。
枚举 $f(1), f(2), \dots, f(M)$。

约束

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

---

输入

输入从标准输入中给出，格式如下：

$N$ $M$

$A_1$ $B_1$

$A_2$ $B_2$

$\vdots$

$A_N$ $B_N$

输出

按照以下格式输出答案：

``` $f(1)$ $f(2)$ $\dots$ $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