CF644B.Processing Queries

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:

1. If server is free and query queue is empty, then server immediately starts to process this query.
2. 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.
3. 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.

本题要求模拟单线程服务器的工作流程。共有 $n$ 个查询需要处理，其中第 $i$ 个查询在时刻 $t_i$ 到达，需耗时 $d_i$ 个单位时间完成处理。所有 $t_i$ 均互不相同。

当一个查询到达时，服务器可能有以下三种反应：

1. 若服务器空闲且查询队列为空，则服务器立即开始处理该查询；
2. 若服务器正忙，且队列中查询数量少于 $b$ 个，则将新查询加入队列尾部；
3. 若服务器正忙，且队列中已有 $b$ 个待处理查询，则新查询被直接拒绝，永不处理。

每当服务器完成某个查询的处理后，它会立即从队列中取出下一个查询（若队列非空）开始处理。若某个新查询恰好在时刻 $x$ 到达，而服务器也恰在时刻 $x$ 完成前一个查询的处理，则我们认为：先从队列中取出下一个查询，之后新查询才到达。

对每个查询，请输出服务器完成其处理的时刻；若该查询被拒绝，则输出 $-1$。

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 ≤ 109), 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.

输入的第一行包含两个整数 $n$ 和 $b$（$1 ≤ n, b ≤ 200\,000$），分别表示查询的总数以及查询队列的最大可能长度。

接下来是 $n$ 行，按时间顺序给出各查询的描述。每行包含两个整数 $t_i$ 和 $d_i$（$1 ≤ t_i, d_i ≤ 10^9$），其中 $t_i$ 表示第 $i$ 个查询到达的时间，$d_i$ 表示服务器处理该查询所需的时间。保证对所有 $i > 1$，均有 $t_{i-1} < t_i$。

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.

输出长度为 $n$ 的整数序列 $e_1,\,e_2,\,...,\,e_n$，其中 $e_i$ 表示服务器完成处理第 $i$ 个查询的时刻（查询按输入中出现的顺序编号），若第 $i$ 个查询被拒绝，则 $e_i = -1$。

Consider the first sample.

1. The server will start to process first query at the moment 2 and will finish to process it at the moment 11.
2. At the moment 4 second query appears and proceeds to the queue.
3. 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.
4. At the moment 11 server will finish to process first query and will take the second query from the queue.
5. At the moment 15 fourth query appears. As the server is currently busy it proceeds to the queue.
6. 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.
7. Server finishes to process query number 4 at the moment 21. Query number 5 is picked from the queue.
8. Server finishes to process query number 5 at the moment 22.

考虑第一个样例。

1. 服务器将在时刻 $2$ 开始处理第一个查询，并在时刻 $11$ 完成对该查询的处理。
2. 在时刻 $4$，第二个查询到达，并进入队列等待。
3. 在时刻 $10$，第三个查询到达。然而，此时服务器仍在处理第一个查询（$b = 1$），且队列中已存在第二个查询，因此第三个查询被直接拒绝。
4. 在时刻 $11$，服务器完成对第一个查询的处理，并从队列中取出第二个查询开始处理。
5. 在时刻 $15$，第四个查询到达。由于服务器当前正忙，该查询进入队列等待。
6. 在时刻 $19$，两个事件同时发生：服务器完成对第二个查询的处理，且第五个查询到达。如题面所述，服务器先完成第二个查询的处理，然后立即从队列中取出第四个查询开始处理，之后第五个查询才到达。此时队列为空，因此第五个查询将被接收并开始处理。
7. 服务器在时刻 $21$ 完成对第四个查询的处理，并从队列中取出第五个查询开始处理。
8. 服务器在时刻 $22$ 完成对第五个查询的处理。