配点 : $700$ 点

問題文

すぬけくんは鉄道会社を運営するゲームで遊ぶことにしました。すぬけ鉄道には $M+1$ 個の駅があり、 $0$ から $M$ までの番号がついています。 すぬけ鉄道の列車は駅 $0$ から $d$ 駅ごとに停車します。 例えば $d = 3$ のとき駅 $0$,駅 $3$,駅 $6$,駅 $9$, $...$ に停車します。

すぬけ鉄道が走っている地域には $N$ 種類の名産品があり、種類 $i$ の名産品は 駅 $l_i$,駅 $l_i+1$,駅 $l_i+2$, $...$, 駅 $r_i$ のいずれかに列車が停車したとき購入することが可能です。

列車が停車する間隔 $d$ は $1, 2, 3, ..., M$ の $M$ 種類が存在しています。 $M$ 種類の列車それぞれについて、その列車に駅 $0$ で乗車した場合に購入可能な名産品の種類数を求めなさい。 なお、列車から別の列車への乗り換えは許されないものとします。

制約

• $1 \leq N \leq 3 \times 10^{5}$
• $1 \leq M \leq 10^{5}$
• $1 \leq l_i \leq r_i \leq M$

入力

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

$N$ $M$

$l_1$ $r_1$

$:$

$l_{N}$ $r_{N}$

出力

答えを $M$ 行に出力せよ。 $i$ 行目では $i$ 駅ごとに停車する列車に乗った場合に購入可能な名産品の種類数を出力せよ。

3 3
1 2
2 3
3 3

3
2
2

• $1$ 駅ごとに停車する列車に乗った場合、種類 $1,2,3$ の $3$ 種類の名産品を購入することが可能です。
• $2$ 駅ごとに停車する列車に乗った場合、種類 $1,2$ の $2$ 種類の名産品を購入することが可能です。
• $3$ 駅ごとに停車する列車に乗った場合、種類 $2,3$ の $2$ 種類の名産品を購入することが可能です。

7 9
1 7
5 9
5 7
5 9
1 1
6 8
3 4

7
6
6
5
4
5
5
3
2