背景

大柱大佬是嘉庚信院最强的大佬之一，不仅如此他还因为美貌火遍了信院（或者说是整个嘉庚学院）。正所谓人红是非多，他经常要处理一些不可告人的事，而且这些事情还没完没了。

大柱大佬比较懒不想自己安排这一切，想凭借自己C++课上学来的“三脚猫的功夫”设计一个任务系统。这个系统是为了定时提醒他去完成这些不可告人的事请。

系统大致如下，初始的时候，大柱大佬可能会注册很多任务，每一个任务的注册如下:

Q_num Period

表示从系统启动开始，每过 Period 秒提醒大柱大佬完成编号为 Qnum的任务。

你能计算出他最先被提醒的 k 个任务吗？

格式

输入

第一行输入一个n(0 < n < 3000)，k(0 < k < 10000)，其中n表示他注册的任务数量。
接下来n行，每行输入一条注册命令，0 < Q_num < 3000，0 < Period < 3000。

输出

顺序输出k行，表示依次提醒的任务的编号。如果同一时间有多个任务，最先提醒编号小的。

样例

输入

2 5
2004 200
2005 300

输出

2004
2005
2004
2004
2005

提示

优先队列