题目描述

すぬけ君决定玩一个经营铁路公司的游戏。すぬけ铁路有 $M+1$ 个车站，编号从 $0$ 到 $M$。すぬけ铁路的列车每隔 $d$ 个车站停靠一次，从车站 $0$ 开始。例如，当 $d=3$ 时，列车会停靠在车站 $0$、车站 $3$、车站 $6$、车站 $9$，以此类推。

すぬけ铁路所在的地区有 $N$ 种特产，第 $i$ 种特产可以在列车停靠于车站 $l_i$、$l_i+1$、$l_i+2$、……、$r_i$ 的任意一个车站时购买。

列车的停靠间隔 $d$ 有 $1,2,3,\ldots,M$ 共 $M$ 种。对于每种停靠间隔 $d$，请你求出如果在车站 $0$ 上车，能够购买到的特产种类数。注意，不能在途中换乘其他列车。

输入格式

输入通过标准输入给出，格式如下：

$N$ $M$
$l_1$ $r_1$
$l_2$ $r_2$
$\vdots$
$l_N$ $r_N$

输出格式

请输出 $M$ 行。第 $i$ 行输出当乘坐每隔 $i$ 个车站停靠的列车时，能够购买到的特产种类数。

样例 1

输入

3 3
1 2
2 3
3 3

输出

3
2
2

样例 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

说明/提示

限制条件

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

样例说明 1

• 当乘坐每隔 $1$ 个车站停靠的列车时，可以购买第 $1,2,3$ 种共 $3$ 种特产。
• 当乘坐每隔 $2$ 个车站停靠的列车时，可以购买第 $1,2$ 种共 $2$ 种特产。
• 当乘坐每隔 $3$ 个车站停靠的列车时，可以购买第 $2,3$ 种共 $2$ 种特产。

由 ChatGPT 4.1 翻译