题目描述

一台测量仪的单位刻度长度为正整数 $x$。测量一段实际长度为 $a$ 的物体时，测量仪先计算 $\dfrac{a}{x}$，再将结果四舍五入到最近的整数，得到显示值。

本题规定：对于非负实数 $y$，若整数 $k$ 满足

则 $y$ 的四舍五入结果为 $k$。因此，恰好位于两个整数正中间的数会舍入到较大的整数。

现有 $n$ 条校准记录。第 $i$ 条记录给出物体的实际长度 $a_i$ 和记录的显示值 $b_i$。

对于每个整数候选刻度长度 $x=1,2,\ldots,m$，分别用这个 $x$ 检验所有记录。如果 $\dfrac{a_i}{x}$ 的四舍五入结果为 $b_i$，就称第 $i$ 条记录与 $x$ 相符。

请对每个候选值 $x$，求出与它相符的记录条数。

输入格式

从文件 scale.in 中读取数据。

第一行包含两个正整数 $n,m$，分别表示校准记录数和候选刻度长度的上界。

接下来 $n$ 行，第 $i$ 行包含两个正整数 $a_i,b_i$，表示第 $i$ 条记录中的实际长度和显示值。

输出格式

输出到文件 scale.out 中。

输出一行 $m$ 个整数。第 $x$ 个整数表示与候选刻度长度 $x$ 相符的记录条数。

5 8
5 2
8 3
10 2
4 1
3 5

0 0 3 1 2 2 1 1

样例解释

• 记录 $(5,2)$ 只与 $x=3$ 相符；
• 记录 $(8,3)$ 只与 $x=3$ 相符；
• 记录 $(10,2)$ 与 $x=5,6$ 相符；
• 记录 $(4,1)$ 与 $x=3,4,5,6,7,8$ 相符；
• 记录 $(3,5)$ 不与任何候选值相符。

例如，当 $a=5,x=2$ 时，$\dfrac{a}{x}=2.5$，按照题目规定应舍入为 $3$，而不是 $2$。

数据规模与约定

对于所有数据，保证 $1\le n,m\le 2\times 10^5$，且 $1\le a_i,b_i\le 10^9$。

本题采用子任务捆绑计分：只有通过一个子任务的全部测试点，才能获得该子任务的分数。

下发文件

下载三组测试数据，非真实测试数据