九条可怜是一个喜欢出题的女孩子，这道题是一道有关浙江省选的硬核模拟题。
在$9102$年，有$n$名选手参加了浙江省选，其中第$i$个选手的智力是$a_i$，训练量是$b_i$。作为 出题人，可怜可以自由选择这套题的风格是比较偏套路还是比较偏智力。举例来说，$ZJOI2018$的题就比较偏智力，今年的题就比较偏套路。
为了定量衡量一套题的风格，可怜定义了反向选拔指数$x$，$x$是一个非负整数。第$i$个选手在反向选拔指数为$x$的题目上的表现为$a_ix+b_i$。在$x$给定的情况下，第$i$个人的排名为表现严格大于$a_ix+bi$的人数再加一。
在$9102$年浙江省队的人数为$m$，因此只有排名小于等于$m$的人才能够进入浙江省队。注意当有并列的情况时，进入浙江省队的人数可能多于$m$。
不难发现，选手的排名和$x$的关系非常大。现在，可怜想让你计算，第$i$个选手有没有可能进入浙江省队，如果有可能，他最好的排名是多少。

第一行输入两个整数$n,m(m\leq n)$，表示选手总数以及浙江省队的人数。
接下来$n$行每行两个整数$a_i,b_i$，表示每个选手的属性值。

输出一行$n$个整数，如果第$i$个选手进不了浙江省队，就输出$-1$，否则输出他可能的最好排名。

3 1
1 5
5 1
2 2

1 1 -1