問題文

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

入力例 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