102604: [AtCoder]ABC260 E - At Least One

Problem Statement

You are given an integer $M$ and $N$ pairs of integers $(A_1, B_1), (A_2, B_2), \dots, (A_N, B_N)$.
For all $i$, it holds that $1 \leq A_i \lt B_i \leq M$.

A sequence $S$ is said to be a good sequence if the following conditions are satisfied:

• $S$ is a contiguous subsequence of the sequence $(1,2,3,..., M)$.
• For all $i$, $S$ contains at least one of $A_i$ and $B_i$.

Let $f(k)$ be the number of possible good sequences of length $k$.
Enumerate $f(1), f(2), \dots, f(M)$.

Constraints

• $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$
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

$N$ $M$
$A_1$ $B_1$
$A_2$ $B_2$
$\vdots$
$A_N$ $B_N$

Output

Print the answers in the following format:

$f(1)$ $f(2)$ $\dots$ $f(M)$

Sample Input 1

3 5
1 3
1 4
2 5

Sample Output 1

0 1 3 2 1

Here is the list of all possible good sequences.

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

Sample Input 2

1 2
1 2

Sample Output 2

2 1

Sample Input 3

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

Sample Output 3

0 0 1 2 4 4 3 2 1

问题描述

你被给出了一个整数$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