Reverse Selection Index

In the year (9102), there are (n) contestants in the Zhejiang Province selection. The (i)-th contestant has an intelligence value (a_i) and a training amount (b_i). The problem setter can choose the style of the problems by setting a nonnegative integer parameter (x) called the reverse selection index. Under index (x), the performance of the (i)-th contestant is defined as [ f_i(x) = a_i, x + b_i, ] and the ranking of contestant (i) is determined as [ \text{rank}_i(x) = 1 + #{ j \mid f_j(x) > f_i(x) }. ] A contestant makes it into the Zhejiang Province team if his/her ranking is less than or equal to (m) (note that ties may lead to more than (m) contestants being selected).

For each contestant, your task is to determine whether there exists a nonnegative integer (x) such that they can enter the team (i.e. obtain a ranking (\le m)). If it is possible, output the best (i.e. smallest) ranking that contestant can achieve among all (x \ge 0); otherwise, output (-1).

Note: When two contestants have equal performance, they are assigned the same ranking (which is (1) plus the number of contestants with strictly greater performance).

inputFormat

The first line contains two integers (n) and (m) (the number of contestants and the number of spots on the team). Each of the following (n) lines contains two integers (a_i) and (b_i), representing the intelligence and training amount of the (i)-th contestant.

outputFormat

Output (n) lines. The (i)-th line should contain the best possible ranking (a positive integer) the (i)-th contestant can achieve over some choice of (x \ge 0) provided that the ranking does not exceed (m). If the contestant cannot ever get a ranking (\le m), output (-1) instead.

sample

3 2
1 2
2 1
1 1

1
1
2