题目描述

有一条单线程的生产线，即同时只能处理一项工作，有 $n$ 个工作申请，第 $i$ 个工作的开始时间为 $t_i$，完成需要 $d_i$ 个单位时间，所有的 $t_i$ 都不相同。

当一项工作申请出现时，生产线会有如下三种处理方案：

1. 如果生产线是空闲的，而且等待队列是空的，则当前申请的工作会被马上执行。
2. 如果生产线正在工作，而且等待队列中的工作少于 $b$ 个，则当前申请的工作会被加入到等待队列的队尾。
3. 如果生产线正在工作，而且等待队列中的工作已经有 $b$ 个，则当前申请的工作会被拒绝，而且再也不会接受该工作的申请。

输入格式

第一行，两个整数 $n$ 和 $b$，$1 \leq n,b \leq 2\times 10^5$。

接下来 $n$ 行，每行两个整数 $t_i$ 和 $d_i$，$1\leq t_i,d_i \leq 10^9$，$t_{i-1}<t_i$。

输出格式

输出共一行，包含 $n$ 个整数，依次表示 $n$ 个工作的完成时间，如果当前工作被拒绝则输出 $-1$。

5 1
2 9
4 8
10 9
15 2
19 1

11 19 -1 21 22

4 1
2 8
4 8
10 9
15 2

10 18 27 -1