You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题面翻译

给你$M$和$N$对整数$(A_1, B_1), (A_2, B_2)\ldots(A_n,B_n)$。

对于所有的$i$，保证$1 \le A_i < B_i \le M$。

如果序列$S$满足以下条件，序列$S$将被称为“好序列”：

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

令$f(k)$为长度为$k$的“好序列”的总数，请求出$f(1),f(2) \ldots f(M)$并输出

题目描述

整数 $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$ の少なくとも一方を含んでいる。

長さ $k$ の良い数列としてあり得るものの個数を $f(k)$ とします。 $f(1),\ f(2),\ \dots,\ f(M)$ を列挙してください。

输入格式

入力は以下の形式で標準入力から与えられる。

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

输出格式

答えを以下の形式で出力せよ。

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

样例 #1

样例输入 #1

3 5
1 3
1 4
2 5

样例输出 #1

0 1 3 2 1

样例 #2

样例输入 #2

1 2
1 2

样例输出 #2

2 1

样例 #3

样例输入 #3

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

样例输出 #3

0 0 1 2 4 4 3 2 1

提示

制約

• $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$
• 入力される値はすべて整数

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