Keli is a girl who loves creating problems, and this is a hardcore simulation problem related to the Zhejiang Provincial Selection.

In the year 9102, $n$ contestants participated in the Zhejiang Provincial Selection, where the $i$-th contestant has intelligence $a_i$ and training volume $b_i$. As the problem setter, Keli can freely choose the style of the problem set, whether it leans more towards "routine" or "intelligence." For example, the problems in ZJOI2018 were more intelligence-oriented, while this year's problems are more routine-oriented.

To quantitatively measure the style of a problem set, Keli defines an "inverse selection index" $x$, where $x$ is a non-negative real number. The performance of the $i$-th contestant on a problem set with an inverse selection index $x$ is $a_i x + b_i$. Given $x$, the rank of the $i$-th person is defined as the number of people whose performance is strictly greater than $a_i x + b_i$, plus one.

The number of people in the Zhejiang provincial team in 9102 is $m$, so only those with a rank less than or equal to $m$ can enter the provincial team. Note that in the case of ties, the number of people entering the provincial team may be greater than $m$.

It is not difficult to see that a contestant's rank is highly dependent on $x$. Now, Keli wants you to calculate whether it is possible for the $i$-th contestant to enter the Zhejiang provincial team, and if so, what their best possible rank is.

Input

The first line contains two integers $n, m$ ($m \le n$), representing the total number of contestants and the number of people in the Zhejiang provincial team.

The next $n$ lines each contain two integers $a_i, b_i$, representing the attribute values of each contestant.

Output

Output a single line containing $n$ integers. If the $i$-th contestant cannot enter the Zhejiang provincial team, output $-1$; otherwise, output their best possible rank.

Examples

Input 1

3 1
1 5
5 1
2 2

Output 1

1 1 -1

Note

When $x = 1$, the performances of the three people are $6, 6, 4$. At this time, the first two are tied for first place and can both enter the provincial team, while the third person is ranked third and cannot enter the provincial team.

When $x > 1$, the second person's performance is strictly better than the third person's, and when $x = 0$, the first person's performance is strictly better than the third person's. Therefore, no matter what value $x$ takes, the third person cannot enter the provincial team.

Constraints

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

For 100% of the data, it is guaranteed that the contestants' attributes are distinct, i.e., $\forall 1 \le i < j \le n$, $a_i \neq a_j$ or $b_i \neq b_j$.