分数: 700 点
问题陈述
Snuke 决定玩一款游戏,玩家经营一家铁路公司。 有 Snuke Line 上的 M+1 车站,编号 0 通过 M。 Snuke Line 上的一列火车停靠在车站 0 和每个 d此后第 1 站,其中 d 是每列列车的预定常数。 例如,如果 d = 3,火车到站 0, 3, 6, 9等等。
有 N Snuke Line 周边地区出售的各种纪念品。 i第一种纪念品可以在火车停靠以下车站之一时购买: 车站 l_i, l_i+1, l_i+2, ..., r_i.
有 M 的值 d,两个站点之间的间隔,对于 Snuke Line 上的火车: 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
- 如果乘坐火车每站停靠,可以购买三种纪念品: 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