问题描述

小健决定玩一个游戏，在这个游戏中，玩家运营一个铁路公司。在Snuke线上有 $M+1$ 个车站，编号为0到 $M$。Snuke线上的火车会在0号站以及之后每隔 $d$ 站停靠，其中 $d$ 是每列火车预先确定的常数。例如，如果 $d = 3$，则火车会停靠在0、3、6、9号站等。

沿Snuke线路的周边地区共售卖 $N$ 种纪念品。第 $i$ 种纪念品可以在以下车站购买：从 $l_i$ 站到 $r_i$ 站（包括 $l_i$ 和 $r_i$）。

在Snuke线上有 $M$ 个不同的 $d$ 值，即火车停靠间隔：1、2、3、...、$M$。对于这些 $M$ 个值中的每一个，找出如果乘坐在0站出发每隔 $d$ 站停靠的火车，能购买的纪念品种类数量。这里假设不允许换乘其他火车。

约束条件

• $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$
• 接下来 $N$ 行：每行为 $l_i$ $r_i$

输出格式

输出共 $M$ 行。第 $i$ 行应包含如果乘坐每隔 $i$ 站停靠的火车，可以购买的最多纪念品种类数量。

样例输入 1

3 3
1 2
2 3
3 3

样例输出 1

3
2
2

如果乘坐每站都停的火车，可以购买三种纪念品：第1、2和3种。 如果乘坐每隔一站停的火车，可以购买两种纪念品：第1和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