← 返回题目列表

AtCoder · arc068_c

E. 蛇核线

中文机器翻译题面 查看原题

分数: 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