I found an interesting problem on https://codeforces.com/problemset/problem/644/B:
In this problem you have to simulate the workflow of one-thread server. There are n queries to process, the i-th will be received at moment t_{i} and needs to be processed for d_{i} units of time. All t_{i} are guaranteed to be distinct.

When a query appears server may react in three possible ways:   If server is free and query queue is empty, then server immediately starts to process this query.  If server is busy and there are less than b queries in the queue, then new query is added to the end of the queue.  If server is busy and there are already b queries pending in the queue, then new query is just rejected and will never be processed. 

As soon as server finished to process some query, it picks new one from the queue (if it's not empty, of course). If a new query comes at some moment x, and the server finishes to process another query at exactly the same moment, we consider that first query is picked from the queue and only then new query appears.

For each query find the moment when the server will finish to process it or print -1 if this query will be rejected.


-----Input-----

The first line of the input contains two integers n and b (1 ≤ n, b ≤ 200 000) — the number of queries and the maximum possible size of the query queue.

Then follow n lines with queries descriptions (in chronological order). Each description consists of two integers t_{i} and d_{i} (1 ≤ t_{i}, d_{i} ≤ 10^9), where t_{i} is the moment of time when the i-th query appears and d_{i} is the time server needs to process it. It is guaranteed that t_{i} - 1 < t_{i} for all i > 1.


-----Output-----

Print the sequence of n integers e_1, e_2, ..., e_{n}, where e_{i} is the moment the server will finish to process the i-th query (queries are numbered in the order they appear in the input) or  - 1 if the corresponding query will be rejected.


-----Examples-----
Input
5 1
2 9
4 8
10 9
15 2
19 1

Output
11 19 -1 21 22 

Input
4 1
2 8
4 8
10 9
15 2

Output
10 18 27 -1 



-----Note-----

Consider the first sample.   The server will...

I tried it in Python, but could not do it. Can you solve it?
import collections 
class TaskMgr:
    def __init__(self, n, b):
        self.b = b
        self.lock_until = 1
        self.q = collections.deque()
        self.end = [-1 for i in range(n)]
    def empty(self):
        return len(self.q) == 0
    def full(self):
        return len(self.q) == self.b
    def add(self, i, t, d):
        if self.full(): return
        self.q.append( (i, t, d) )
    def tick(self, now=None):
        if self.empty(): return
        lock = self.lock_until
        now  = now or lock
        if now < lock:   return
        now = min(lock, now)
        i, t, d = self.q.popleft()
        t = max(t, now)
        end = t + d
        self.lock_until = end
        self.end[i]     = end
def __starting_point():
    n, b = [int(x) for x in input().split()]
    mgr  = TaskMgr(n, b)
    for i in range(n):
        t, d = [int(x) for x in input().split()]
        mgr.tick(t)
        mgr.add(i, t, d)
    while not mgr.empty(): mgr.tick()
    print(' '.join(str(x) for x in mgr.end))

__starting_point()