浙江省选

题号：NC25540
时间限制：C/C++/Rust/Pascal 5秒，其他语言10秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

九条可怜是一个喜欢出题的女孩子，这道题是一道有关浙江省选的硬核模拟题。

在9102年，有n名选手参加了浙江省选，其中第i个选手的智力是 $a_i$ ，训练量是 $b_i$ 。作为出题人，可怜可以自由选择这套题的风格是比较偏套路还是比较偏智力。举例来说，ZJOI2018的题就比较偏智力，今年的题就比较偏套路。

为了定量衡量一套题的风格，可怜定义了反向选拔指数x，x是一个非负整数。第i个选手在反向选拔指数为x的题目上的表现为 $a_{i}x+b_{i}$ 。在x给定的情况下，第i个人的排名为表现严格大于 $a_{i}x+b_{i}$ 的人数再加一。

在9102年浙江省队的人数为m，因此只有排名小于等于m的人才能够进入浙江省队。注意当有并列的情况时，进入浙江省队的人数可能多于m。

不难发现，选手的排名和x的关系非常大。现在，可怜想让你计算，第i个选手有没有可能进入浙江省队，如果有可能，他最好的排名是多少。

第一行输入两个整数，表示选手总数以及浙江省队的人数。 
接下来 n 行每行两个整数，表示每个选手的属性值。

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

示例1

复制

复制

1 1 -1

当 x = 1 时，三个人的表现分别为 6,6,4，这时前两个人并列第一名，都能进入省队，而第三个人排名第三，没法进入省队。
当 x > 1 时，第二个人的表现严格好于第三个人，而当 x = 0 时，第一个人的表现严格好于第三个人，因此第三个人无论 x 怎么取，他都没有办法进入省队。