问题描述

Snuke决定玩一个游戏，在这个游戏中，玩家经营一家铁路公司。在Snuke线路上有$M+1$个车站，编号从$0$到$M$。Snuke线路上的列车会在第$0$个车站和以后每$d$个车站停下来，其中$d$是每辆列车的预定常数。例如，如果$d=3$，则列车会在第$0$、$3$、$6$、$9$等车站停下来。

在Snuke线路周围的区域有$N$种纪念品出售。当列车在以下车站之一停下时，可以购买第$i$种纪念品：车站$l_i$，$l_i+1$，$l_i+2$，$...$，$r_i$。

Snuke线路上的列车有$M$个间隔值$d$，即两个停靠站之间的间隔：$1$，$2$，$3$，$...$，$M$。对于这$M$个值中的每一个，求出如果乘坐该值的$d$在第$0$个车站停靠的列车，可以购买的纪念品种类数。在这里，假设不允许换乘。

约束条件

• $1 ≦ N ≦ 3 × 10^{5}$
• $1 ≦ M ≦ 10^{5}$
• $1 ≦ l_i ≦ r_i ≦ M$

输入

输入以以下格式从标准输入中给出：

$N$ $M$ $l_1$ $r_1$ $:$ $l_{N}$ $r_{N}$

输出

按照每$M$行，输出结果。第$i$行应该包含如果乘坐在每第$i$个车站停靠的列车时可以购买到最多的纪念品种类数。

示例输入 1

3 3
1 2
2 3
3 3

示例输出 1

3
2
2

• 如果乘坐在每个车站停靠的列车上，可以购买到$3$种纪念品：第$1$、$2$、$3$种。
• 如果乘坐在每两个车站停靠的列车上，可以购买到$2$种纪念品：第$1$和第$2$种。
• 如果乘坐在每三个车站停靠的列车上，可以购买到$2$种纪念品：第$2$和第$3$种。

示例输入 2

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

示例输出 2

7
6
6
5
4
5
5
3
2