在这个问题中你必须模拟单线程服务器的工作流程。有 n 个查询需要处理,第 i 个查询将在 ti 时刻收到,需要处理 di 个时间单位。所有 ti 都保证是不同的。
当查询出现时,服务器可能会以三种可能的方式做出反应:
1. 如果服务器空闲且查询队列为空,则服务器立即开始处理该查询。
2. 如果服务器繁忙并且队列中的查询少于 b 个,则新查询将添加到队列末尾。
3. 如果服务器繁忙并且队列中已经有 b 个查询待处理,则新查询将被拒绝并且永远不会被处理。
服务器一完成处理某个查询,就会从队列中选择新的查询(当然,如果它不为空)。如果在某个时刻 x 出现一个新查询,并且服务器在同一时刻完成处理另一个查询,我们认为第一个查询是从队列中选取的,然后才会出现新查询。
对于每个查询,找到服务器完成处理该查询的时刻,或者如果该查询将被拒绝,则打印 -1。
输入
输入的第一行包含两个整数 n 和 b (1 ≤ n, b ≤ 200 000) - 查询数量和查询队列的最大可能大小。
然后接下来的 n 行是查询描述(按时间顺序)。每个描述由两个整数ti和di组成(1≤ti,di≤109),其中ti是第i个查询出现的时刻,di是服务器需要处理它的时间。对于所有 i > 1,保证 ti - 1 < ti。
输出
打印 n 个整数 e1, e2, ..., en 的序列,其中 ei 是服务器完成处理第 i 个查询的时刻(查询按照它们在输入中出现的顺序进行编号),如果相应的查询将被拒绝,则为 - 1。
示例
输入 #1
5 1 2 9 4 8 10 9 15 2 19 1
输出 #1
11 19 -1 21 22
输入 #2
4 1 2 8 4 8 10 9 15 2
输出 #2
10 18 27 -1
注意
考虑第一个样本。
1. 服务器将在时刻 2 开始处理第一个查询,并在时刻 11 完成处理。
2. 此时出现 4 秒查询并进入队列。
3. 此时出现 10 第三个查询。然而,服务器仍然忙于查询 1,b = 1 并且队列中已经有查询 2 待处理,因此第三个查询被拒绝。
4. 此时,11 服务器将完成第一个查询的处理,并将从队列中取出第二个查询。
5. 此时出现第四个查询15。由于服务器当前正忙,因此它会进入队列。
6. 此时 19 两个事件同时发生:服务器完成第二个查询,出现第五个查询。正如上面的语句中所说,第一个服务器将处理完第二个查询,然后它会从队列中选择第四个查询,然后第五个查询才会出现。由于队列为空,因此将继续进行第五个查询。
7. 服务器在 21 时刻完成对编号 4 的查询的处理。从队列中选取查询编号 5。
8. 服务器在 22 时刻完成对 5 号查询的处理。