Problem D
All Fax No Printer

You have $k$ fax machines. Throughout the day, $n$ jobs arrive in order, each taking a certain amount of time. Each job gets run on a machine if one is available, else must be canceled if none are available at that time. Being a regretful person, you want to know how well you could have done at each point in time if you had made decisions optimally. Instead of just canceling any incoming job, you want to know how many more tasks you could have completed if you had the ability to throw out a task that had already been running. For each $i$, output the positive difference between the maximum number of jobs that could be completed given jobs $1$ through $i$ with this better decision making and the number that actually got run.

A machine is free the instant the job it’s running finishes.

Input

First line contains space-separated integers $n,k$ ($1 \leq n,k \leq 2\cdot 10^5$).

This is followed by $n$ lines representing the order in which the jobs arrived, the $i$th of which contains space-separated integers $t_ i, l_ i$: the time $t_ i$ that job $i$ must be started, and how long it takes $l_ i$ in the same time units. These values satisfy $0 \leq t_ i \leq 2\cdot 10^7$ and $1 \leq l_ i \leq 2\cdot 10^7$.

It is guaranteed that $t_{i+1} \geq t_ i$.

Output

Output $n$ lines, the $i$th of which contains the positive difference between the maximum number of jobs that could be completed given jobs $1$ through $i$ and the number that actually got run.

5 1
1 3
1 1
2 1
3 1
4 2

0
0
1
2
2

5 2
1 3
1 1
2 1
3 1
4 2

0
0
0
0
0