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 start to process first query at the moment 2 and will finish to process it at the moment 11.  At the moment 4 second query appears and proceeds to the queue.  At the moment 10 third query appears. However, the server is still busy with query 1, b = 1 and there is already query 2 pending in the queue, so third query is just rejected.  At the moment 11 server will finish to process first query and will take the second query from the queue.  At the moment 15 fourth query appears. As the server is currently busy it proceeds to the queue.  At the moment 19 two events occur simultaneously: server finishes to proceed the second query and the fifth query appears. As was said in the statement above, first server will finish to process the second query, then it will pick the fourth query from the queue and only then will the fifth query appear. As the queue is empty fifth query is proceed there.  Server finishes to process query number 4 at the moment 21. Query number 5 is picked from the queue.  Server finishes to process query number 5 at the moment 22.

Difficulty: interview

Starter code:

Solutions:
from collections import deque

n, b = map(int, input().split())

q = deque()
for _ in range(n):
    t, d = map(int, input().split())
    while q and q[0] <= t:
        q.popleft()
    if len(q) == b + 1:
        print(-1, end = ' ')
    else:
        if q:
            t = q[-1]
        print(t + d, end = ' ')
        q.append(t + d)


n, b = map(int, input().split())

from collections import deque

q = deque()

for i in range(n):
    t, d = map(int, input().split())
    while len(q) > 0 and q[0] <= t:
        q.popleft()
    if len(q) <= b:
        r = t if len(q) == 0 else q[-1]
        print(r + d, end = ' ')
        q.append(r + d)
    else:
        print(-1, end = ' ')
    


import sys
from collections import deque
# sys.stdin = open("ivo.in")
n, b = map(int, sys.stdin.readline().split())
b += 1
q = deque()
res = []
cur_time = 0
for iter in range(n):
  t, d = map(int, sys.stdin.readline().split())
  while len(q) > 0 and q[0] <= t:
    q.popleft()
  if len(q) >= b:
    res.append(-1)
    continue
  if len(q) == 0:
    res.append(t + d)
    q.append(t + d)
  else:
    res.append(q[-1] + d)
    q.append(q[-1] + d)
print(" ".join(map(str, res)))

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()

def main():
    from collections import deque
    a = deque()
    n, b = map(int, input().split())
    next_t = 0
    for i in range(n):
        c, lo = map(int, input().split())
        while a and a[0] <= c:
            a.popleft()
        if len(a) > b:
            print(-1, end=' ')
        else:
            print(max(next_t, c) + lo, end=' ')
            next_t = max(next_t, c) + lo
            a.append(next_t)
main()

n,b=map(int,input().split())
l=[tuple(map(int,input().split())) for i in range(n)]
ch=[0]
ans=[]
bd=[0]*(n+1)
po=ma=0
for i in range(n):
    t,d=l[i]
    bd[i]=bd[i-1]
    ch+=[max(ma,t)+d]
    while ch[po]<=t: po+=1
    if i-po-(bd[i-1]-bd[po-1])==b: bd[i]+=1; ch[-1]=-1
    if ch[-1]>ma: ma=ch[-1]
    ans+=[str(ch[-1])]
print(' '.join(ans))

#! /usr/bin/env python3
'''
' Title:	
' Author:	Cheng-Shih, Wong
' Date:		
'''
from collections import deque

n, b = list(map(int, input().split()))

query = {}
tm = []
que = deque()
ans = {}

for i in range(n):
	u, v = list(map(int, input().split()))
	query[u] = v
	tm.append(u)

et = 0

for ti in tm:
	while ti>et and len(que)>0:
		cur = que.popleft()
		et += query[cur]
		ans[cur] = et

	if ti>et:
		et = ti+query[ti]
		ans[ti] = et
	elif ti==et:
		if len(que) > 0:
			cur = que.popleft()
			et = ti+query[cur]
			ans[cur] = et
		que.append(ti)
	else:
		if len(que) >= b:
			ans[ti] = -1
		else:
			que.append(ti)

while len(que)>0:
	cur = que.popleft()
	et += query[cur]
	ans[cur] = et

outs = ''
space = False

for ti in tm:
	if space: outs += ' '
	else: space = True
	outs += str(ans[ti])

print(outs)
		


from collections import deque

n, b = [int(x) for x in input().split()]
d = deque()
ans = [0] * n
now = 0
j = 0
for i in range(n):
    t = [int(x) for x in input().split()]
    while len(d) != 0 and now <= t[0]:
        if d[0][0] > now:
            now = d[0][0] + d[0][1]
        else:
            now += d[0][1]
        d.popleft()
        while ans[j] != 0:
            j += 1
        ans[j] = now
        j += 1
    if len(d) == b:
        ans[i] = -1
    else:
        d.append(t)
while len(d) != 0:
    if d[0][0] > now:
        now =  d[0][0] + d[0][1]
    else:
        now += d[0][1]
    d.popleft()
    while ans[j] != 0:
        j += 1
    ans[j] = now
    j += 1
print(*ans)

from collections import deque
from collections import namedtuple
Query = namedtuple("Query", ["time", "duration"])
query_number, max_query_queue_length = list(map(int, input().split()))
queries = deque(Query(*list(map(int, input().split()))) for i in range(query_number))
results = {}
query_queue = deque()
current_time = 0
while len(results) != query_number:
    if query_queue:
        query = query_queue.popleft()
    else:
        query = queries.popleft()
    if current_time > query.time:
        current_time += query.duration
    else:
        current_time = query.time + query.duration
    results[query.time] = current_time
    while queries and queries[0].time < current_time:
        if len(query_queue) < max_query_queue_length:
            query_queue.append(queries.popleft())
        else:
            ignored_query = queries.popleft()
            results[ignored_query.time] = -1
print(" ".join(str(results[time]) for time in sorted(results.keys())))


3

# def gen(n, b):
# 	import random
# 	yield '{} {}'.format(n, b)
# 	t = 0
# 	for i in range(n):
# 		t += random.randrange(1, 1e7)
# 		d = random.randrange(1, 1e7)
# 		yield '{} {}\n'.format(t, d)

# def input():
# 	g = gen(200000, 200000)

# 	return next(g)

n, b = map(int, input().split())

ends = []

for i in range(n):
	t, d = map(int, input().split())

	while len(ends) > 0 and ends[0] <= t:
		ends.pop(0)

	q = len(ends) - 1

	if q == b:
		print(-1, end=' ')
		continue

	if not ends:
		ends.append(t + d)
	else:
		ends.append(ends[-1] + d)

	print(ends[-1], end=' ')



import sys



def main():
    n, b = [int(tok) for tok in sys.stdin.readline().split()]

    td_list = []
    for i in range(n):
        td_list.append([int(tok) for tok in sys.stdin.readline().split()])

    queue = []
    finish = [-1 for i in range(n)]

    for i, (t, d) in enumerate(td_list):


        if len(queue) > 0:
            if queue[0] <= t:
                queue.pop(0)

        if len(queue) == 0 or queue[-1] < t:
            queue.append(t + d)
            finish[i] = t + d
        elif len(queue) == b + 1:
            pass
        else:
            finish[i] = queue[-1] + d
            queue.append(queue[-1] + d)


    print(" ".join([str(f) for f in finish]))


def __starting_point():
    main()

__starting_point()

import os
s = input().split(' ')
n = int(s[0])
b = int(s[1])

requests = [[]] * n

for i in range(n):
    s = input().split(' ')
    requests[i] = [int(s[0]), int(s[1])]

result = [0] * n
counter = 1
time = 0
queue = []

time = requests[0][0]

queue = [[0, requests[0][1]]]

while(counter < n):
    if(len(queue) != 0):
        if(queue[0][1] <= requests[counter][0] - time):
            time += queue[0][1]
            result[queue[0][0]] = str(time)
            queue = queue[1:]
        else:
            queue[0][1] -= requests[counter][0] - time
            time = requests[counter][0]
            if(len(queue) < b + 1):
                queue += [[counter, requests[counter][1]]]
            else:
                result[counter] = '-1'
            counter += 1
    else:
        time = requests[counter][0]
        queue += [[counter, requests[counter][1]]]
        counter += 1

for i in range(len(queue)):
    time += queue[i][1]
    result[queue[i][0]] = time

print()
s = ''
for i in range(len(result)):
    s += str(result[i]) + ' '
print(s)

n, b = list(map(int, input().split()))
tasks = []
next_task = 0
time = 0
finish = [-1]*n
for i in range(n):
    t, d = list(map(int, input().split()))
    while tasks and next_task < len(tasks) and time <= t:
        time += tasks[next_task][1]
        finish[tasks[next_task][0]] = time
        next_task += 1
    if len(tasks) - next_task < b:
        tasks.append((i, d))
    time = max(t, time)
while tasks and next_task < len(tasks):
    time += tasks[next_task][1]
    finish[tasks[next_task][0]] = time
    next_task += 1
print(*finish)


def main():
    read = lambda: list(map(int, input().split()))
    n, b = read()
    from collections import deque
    Q = deque()
    ans = [0] * n
    for i in range(n):
        t, d = read()
        while len(Q) > 0 and t >= Q[0]:
            Q.popleft()
        if len(Q) == 0:
            cur = t + d
        elif len(Q) < b + 1:
            cur = Q[-1] + d
        else:
            cur = -1
        ans[i] = cur
        if cur != -1:
            Q.append(cur)
    print(' '.join(map(str, ans)))
main()


n, queue_size = [int(x) for x in input().split()]

results = [-1 for _ in range(n)]

next_server_free_time = 1
queue = []
for idx in range(n):
    t, d = [int(x) for x in input().split()]

    while queue and next_server_free_time <= t:
        idx1, d1 = queue.pop(0)
        next_server_free_time += d1
        results[idx1] = next_server_free_time

    if next_server_free_time <= t:
        results[idx] = t + d
        next_server_free_time = t + d
    else:
        if len(queue) < queue_size:
            queue.append((idx, d))

while queue:
    idx, d = queue.pop(0)
    next_server_free_time += d
    results[idx] = next_server_free_time

print(' '.join([str(x) for x in results]))


from collections import deque
n, d  =map(int,(input().split()))
per = input().split()
t = int(per[0])+int(per[1])
per = 0
print(t, end = ' ')
answer = t
queue = deque()
for i in range(n-1):
    per1, per2 = map(int, input().split())
    
    while t< per1:
        if per >= 1:
            s = queue.pop()
            
            t += s
            per-=1
        else:
            t = per1
            answer = t
    if  t == per1:
        if per >= 1:
            s = queue.pop()
            
            per-=1
            t+= s
            if per < d:
                answer+=per2
                print(answer, end = ' ')
                queue.appendleft(per2)
                per+=1
                
        else:
            answer = answer+per2
            print(answer, end = ' ')
            queue.appendleft(per2)
            
            per = 1
        
    else:
        if per < d:
            answer = answer+per2
            queue.appendleft(per2)
            print(answer, end = ' ')
            per+=1
        else:
            print(-1,end = ' ')
        
        


n, b = [int(i) for i in input().split()]
q = [0] * n
bg = 0
en = 0
time = 0
res = [-1] * n
for it in range(n):
    ev = [int(i) for i in input().split()]
    ev.append(it)
    while bg < en and max(time, q[bg][0]) <= ev[0]:
        time = max(time, q[bg][0])
        res[q[bg][2]] = time + q[bg][1]
        time += q[bg][1]
        bg += 1
    if en - bg < b:
        q[en] = ev
        en += 1
        
while bg < en:
    time = max(time, q[bg][0])
    res[q[bg][2]] = time + q[bg][1]
    time += q[bg][1]
    bg += 1

for i in range(n):
    print(res[i], end=' ')


from collections import deque
while True:
	try:
		n, max_queue_lenth = map(int, input().split())
	except EOFError:
		break

	queue = deque()
	responses = []
	for i in range(n):
		time, duration = tuple(map(int, input().split()))
		while queue and queue[0]<=time:
			queue.popleft()
		if not queue:
			queue.append(time+duration)
			responses.append(time+duration)
			continue
		else:
			if len(queue)<=max_queue_lenth:
				queue.append(queue[-1]+duration)
				responses.append(queue[-1])
			else:
				responses.append(-1)
	print(" ".join(map(str, responses)))

from sys import maxsize as m
from itertools import product as P 
class Solution:
    def bazinga(self,N,p):
        pass 

def __starting_point():
    n,b = list(map(int,input().split(' ')))
    ct,pt,lpt,cb = 0,0,[],0
    result = []
    for i in range(n):
        ti,di = list(map(int,input().split()))
        #print(pt,lpt,'--',ti,di,cb)
        res = 0
        if pt==0:
            pt+= ti+di
            lpt += [pt]
            res = pt
        else:
            if ti<lpt[0]:
                if cb<b:
                    pt+= di
                    lpt+=[pt]
                    res = pt
                    cb+=1
                elif cb>=b:
                    res = -1
                    
            elif ti>=lpt[0]:
                #print(lpt,pt,ti,di)
                if ti>lpt[-1]:
                    pt+=abs(lpt[-1]-ti)+di
                else: pt+=di
                lpt+=[pt]
                res = pt
                cb+=1
                while ti>=lpt[0]:
                    if len(lpt)==1: break
                    lpt.pop(0)
                    if cb>0:    cb-=1
                
        result += (str(res),)
    print(' '.join(result))
                
        
        
        
        
            
        
        

        
    

    
        
        
        
            
        


    

__starting_point()

n,b=map(int,input().split())
def Q():
  a=[0];l=0
  for i in range(n):
    t,d=map(int,input().split())
    a+=[t+d if t>a[-1] else a[-1]+d]
    while a[l]<=t: l+=1
    if len(a)-l-1>b: a.pop(); yield "-1"
    else: yield str(a[-1])
print(' '.join(Q()))

import heapq
n, b = map(int, input().split())
ans = [-1 for i in range(n)]
queue = []
head = 0
size = 0
time = 0
for i in range(n):
    t, d = map(int, input().split())
    while size != 0 and time <= t:
        time += queue[head][0]
        ans[queue[head][1]] = time
        head += 1
        size -= 1
    if size == b:
        continue
    if size == 0 and time <= t:
        time = t + d
        ans[i] = time
        continue
    queue.append((d, i))
    size += 1
for i in range(head, len(queue)):
    time += queue[i][0]
    ans[queue[i][1]] = time
for x in ans:
    print(x, end=' ')

n, size = map(int, input().split())
queue = []
head, tail = 0, 0

for i in range(n):
    time, during = map(int, input().split())
    while head != tail and time >= queue[head]:
        head += 1
    if tail - head - 1 < size:
        if head == tail:
            queue.append(time + during)
        else:
            queue.append(queue[-1] + during)
        print(queue[-1], end = ' ')
        tail += 1
    else:
        print('-1', end = ' ')

n, size = map(int, input().split())
queue = []
head, tail = 0, 0

for i in range(n):
    time, during = map(int, input().split())
    while head != tail and time >= queue[head]:
        head += 1
    if tail - head - 1 < size:
        if head == tail:
            queue.append(time + during)
        else:
            queue.append(queue[-1] + during)
        print(queue[-1], end = ' ')
        tail += 1
    else:
        print('-1', end = ' ')

from heapq import heappush, heappop
from collections import deque


number_jobs, queue_size = list(map(int, input().split()))

ret = dict()
events = list()
jobs = deque()

for i in range(number_jobs):
    time, duration = list(map(int, input().split()))
    heappush(events, (time, 1, i, duration))

while events:
    data = heappop(events)

    if data[1] == 0:
        finish_time, job_number = data[0], data[2]
        ret[job_number] = finish_time
        jobs.popleft()

        if jobs:
            job, duration = jobs.popleft()
            jobs.appendleft((job, duration))
            heappush(events, (finish_time + duration, 0, job))
    else:
        time, job_number, duration = data[0], data[2], data[3]

        if len(jobs) <= queue_size:
            if not jobs:
                heappush(events, (time + duration, 0, job_number))
            jobs.append((job_number, duration))
        else:
            ret[job_number] = -1

print(" ".join([str(ret[x]) for x in sorted(ret)]))