AT_arc068_c [ARC068E] Snuke Line

すぬけ君决定玩一个经营铁路公司的游戏。すぬけ铁路有 $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 \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 翻译