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

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

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

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

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

输入格式

第一行输入两个整数 $n,m(m \leq n)$，表示选手总数以及浙江省队的人数。

接下来 $n$ 行每行两个整数 $a_i,b_i$，表示每个选手的属性值。

输出格式

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

样例一

input

3 1
1 5
5 1
2 2

output

1 1 -1

explanation

当 $x = 1$ 时，三个人的表现分别为 $6,6,4$，这时前两个人并列第一名，都能进入省队，而第三个人排名第三，没法进入省队。

当 $x>1$ 时，第二个人的表现严格好于第三个人，而当 $x=0$ 时，第一个人的表现严格好于第三个人，因此第三个人无论 $x$ 怎么取，他都没有办法进入省队。

样例二

见样例数据下载

限制与约定

对于 $100\%$ 的数据，$1 \leq a_i\leq 10^9, 1 \leq b_i \leq 10^{18}$，$1 \leq m \leq n$。

对于 $100\%$ 的数据，保证选手的属性两两不同，即 $\forall 1 \leq i < j\leq n$，有 $a_i \neq a_j$ 或 $b_i \neq b_j$。

时间限制：$5\texttt{s}$

空间限制：$512\texttt{MB}$

下载

样例数据下载