题目描述

政务大厅里有 $n$ 个窗口。第 $i$ 个窗口同时最多服务 $a_i$ 人，每名群众办理 $b_i$ 分钟后离开。

现在有 $m$ 名群众同时到达，并按到达的先后顺序依次选择窗口。每名群众都会选择“预计等待时间最短”的窗口：

• 如果窗口里还能容纳（正在办理的群众少于 $a_i$），等待时间记为 $0$；
• 否则需要等里面的人离开，第一批离开要等 $b_i$ 分钟，之后每多等一批再增加 $b_i$ 分钟。

如果两个窗口的等待时间相同，群众选择编号较小的窗口。

规定在所有人选完窗口之前，没有人离开大厅。请输出此时每个窗口外排队的人数。

输入格式

第一行包含两个整数 $n$ 和 $m$，分别表示窗口的数量和群众数量。

接下来 $n$ 行，每行两个正整数 $a_i$ 和 $b_i$，含义如上所述。

输出格式

输出一行 $n$ 个整数，依次表示每个窗口外排队的人数，相邻两个数之间用一个空格隔开。

样例

2 10
1 2
3 5

3 3

3 25
2 4
1 6
5 3

4 1 12

3 25
5 3
2 4
1 6

12 4 1

样例解释

样例 1 中，1 号窗口先接待 1 人、2 号窗口先接待 3 人；之后 1 号窗口每 2 分钟、2 号窗口每 5 分钟释放一批名额。第 10 名群众等待 6 分钟进入 1 号窗口，最终两个窗口外各有 $3$ 人。

样例 2 中，前三批名额被占满后，群众继续按等待时间排队，三个窗口外分别有 $4,1,12$ 人。

样例 3 将样例 2 的窗口按原第 3、1、2 个的顺序重新编号。本例中，对应窗口的排队人数不变，按新编号依次输出 $12,4,1$。

数据范围与约定

对于 $100\%$ 的数据，$1\le n\le 10^5$，$1\le m\le 10^9$，$1\le a_i,b_i\le 10^9$。