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

長さ $k$ の良い数列としてあり得るものの個数を $f(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