题目描述

给定整数 $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)$

示例输入 1

3 5
1 3
1 4
2 5

示例输出 1

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)$

示例输入 2

1 2
1 2

示例输出 2

2 1

示例输入 3

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

示例输出 3

0 0 1 2 4 4 3 2 1