Description

Kyuukawa Karen is a girl who likes to create problems. This problem is a hardcore simulation problem about the Zhejiang NOI Qualifier.

In the year $9102$, there are $n$ contestants participating in the Zhejiang NOI Qualifier. The $i$-th contestant has intelligence $a_i$ and training amount $b_i$. As the problem setter, Karen can freely choose whether this set of problems is more “pattern-based” or more “intelligence-based”. For example, the problems in ZJOI 2018 were more intelligence-based, while this year’s problems are more pattern-based.

To measure the style of a set of problems quantitatively, Karen defines the reverse selection index $x$, where $x$ is a non-negative integer. The performance of the $i$-th contestant on problems with reverse selection index $x$ is $a_ix+b_i$. When $x$ is fixed, the rank of the $i$-th person is the number of people whose performance is strictly greater than $a_ix+b_i$, plus one.

In the year $9102$, the size of the Zhejiang provincial team is $m$, so only those with rank $\le m$ can enter the team. Note that when there are ties, the number of people who enter the team may be greater than $m$.

It is not hard to see that a contestant’s rank depends heavily on $x$. Now, Karen wants you to compute whether the $i$-th contestant can possibly enter the Zhejiang provincial team. If possible, what is their best possible rank.

Input Format

The first line contains two integers $n,m(m\leq n)$, representing the total number of contestants and the size of the Zhejiang provincial team.
The next $n$ lines each contain two integers $a_i,b_i$, representing each contestant’s attributes.

Output Format

Output one line with $n$ integers. If the $i$-th contestant cannot enter the Zhejiang provincial team, output $-1$. Otherwise, output their best possible rank.

3 1
1 5
5 1
2 2

1 1 -1

Hint

Constraints

Explanation of Sample 1

When $x=1$, the three contestants’ performances are $6,6,4$. At this time, the first two contestants are tied for 1st place, and both can enter the provincial team. The third contestant ranks 3rd and cannot enter.

When $x>1$, the second contestant’s performance is strictly better than the third contestant’s. When $x=0$, the first contestant’s performance is strictly better than the third contestant’s. Therefore, no matter how $x$ is chosen, the third contestant has no way to enter the provincial team.

Constraints and Notes

For $100\%$ of the data, $1\leq a_i \leq 10^9$, $1\leq b_i \leq 10^{18}$, and $1\leq m \leq n$.

For $100\%$ of the data, it is guaranteed that all contestants’ attributes are pairwise different, i.e., $\forall 1\leq i < j \leq n$, we have $a_i\neq a_j$ or $b_i\neq b_j$.

Translated by ChatGPT 5