题目描述

节假日到了，商场人数爆满，每家店前面都排了很长的队伍。桃子想要快速评估哪一家店排队人数最多，于是她做了一个统计，得出了一些信息。

商场共有 $n$ 家店，第 $i$ 家店可以同时容纳 $a_i$ 个人，每个人需要在店里待 $b_i$ 分钟就会离开。当某一个人进入商场时，会评估哪家店排队时间最少，并选择最少的店进入或者排队（如果店内有空位，则认为排队时间为 0）。如果两家店排队时间相同，则进入编号较小的一家店。

现在有 $m$ 个人同时$^*$进入了商场并按顺序选择了自己的店铺，请输出每个店铺此时排队了几个人。

$^*$同时：此处的同时强调的是没有任何一个人在店里待了 $b_i$ 时间而离开，即你可以认为没有人离开过店铺。

输入格式

输入第一行给定三个整数 $n,m$，表示共有 $n$ 家店铺，$m$ 个人。

接下来有 $n$ 行，每行给出两个正整数，分别表示 $a_i, b_i$。

输出格式

输出一行 $n$ 个用空格隔开的整数表示结果。

3 18
1 3
2 5
10 20

3 2 0

说明

首先 13 个人占满三家店铺的所有空位。第 14 个人在第一家店铺排队（因为等待时间为 3 分钟）。第 15、16 个人在第二家店铺排队（因为这两个人的等待时间都是 5 分钟）。第 17、18 个人在第一家店铺排队（等待时间分别是 6、9 分钟）

3 35
1 3
2 5
10 20

6 8 8

3 35
1 3
10 20
2 5

6 10 6

说明

等待时间相同时，编号小的店铺优先排队

测试点说明

大样例

T3sample