结果比较方式为全文比较（过滤行末空格及文末换行）。

题目描述

街角的打印店只有一台打印机。某天店里共收到 $n$ 个打印任务，编号为 $1 \sim n$。第 $i$ 个任务在时刻 $a_i$ 送达柜台（到达时刻两两不同，任务按到达先后给出），需要打印 $p_i$ 页。打印机从时刻 $0$ 起开始工作，打印 $1$ 页恰好耗时 $1$ 分钟。

店里对打印顺序立下如下规矩：打印一个任务时中途不得打断；打印机一旦空闲，若存在已到达且未完成的任务，必须立刻从中挑选一个开始打印，不得刻意空转等待。

店规把页数达到 $K$ 及以上的任务列为急件。挑选下一个任务时，若已到达且未完成的急件非空，必须在急件之中挑选；只有当没有已到达且未完成的急件时，才可以在其余任务中挑选。无论在哪一类中挑选，都优先选页数最少的任务；若页数相同，则选到达最早的任务。

请你求出每个任务的完成时刻，即该任务最后一页打印完毕的时刻。

输入格式

从文件 print.in 中读入数据。

• 第一行两个整数 $n, K$，表示任务数量与急件页数界限；
• 接下来 $n$ 行，每行两个整数 $a_i, p_i$，依次表示第 $i$ 个任务的到达时刻与页数。任务按到达时刻升序给出。

输出格式

输出到文件 print.out 中。

输出 $n$ 行，第 $i$ 行一个整数，表示第 $i$ 个任务的完成时刻。

样例

4 5
0 3
1 8
2 2
4 6

3
11
19
17

样例 1 解释

时刻 $0$ 只有任务 $1$ 已到达，打印机在时刻 $0\sim3$ 打印任务 $1$。此后任务 $2$（$8$ 页，急件）与任务 $3$（$2$ 页，普通件）都已到达，急件非空，故在时刻 $3\sim11$ 打印任务 $2$；期间任务 $4$（$6$ 页，急件）也已到达。时刻 $11$ 时已到达的急件中只有任务 $4$，于是在时刻 $11\sim17$ 打印任务 $4$，最后在时刻 $17\sim19$ 打印任务 $3$。

4 10
0 12
2 12
3 12
50 5

12
24
36
55

样例 2 解释

时刻 $0$ 只有任务 $1$ 已到达，打印机在时刻 $0\sim12$ 打印任务 $1$。时刻 $12$ 时任务 $2$、$3$ 都已到达，页数同为 $12$，选到达最早的任务 $2$，在时刻 $12\sim24$ 打印；随后在时刻 $24\sim36$ 打印任务 $3$。任务 $4$ 要到时刻 $50$ 才到达，打印机在时刻 $36\sim50$ 空闲等待，最后在时刻 $50\sim55$ 打印任务 $4$。

4 6
0 8
1 6
2 1
3 7

8
14
22
21

样例 3 解释

时刻 $0$ 只有任务 $1$ 已到达，打印机在时刻 $0\sim8$ 打印任务 $1$。时刻 $8$ 时其余三个任务都已到达：任务 $2$ 有 $6$ 页、任务 $4$ 有 $7$ 页，均属急件；任务 $3$ 只有 $1$ 页，是普通件。急件非空，故只在任务 $2$、$4$ 中挑选，页数更少的任务 $2$ 在时刻 $8\sim14$ 打印；随后任务 $4$ 在时刻 $14\sim21$ 打印；最后没有急件剩余，任务 $3$ 在时刻 $21\sim22$ 打印。

数据范围

对于所有测试数据，保证：

• $1 \le n \le 10^5$；
• $0 \le a_1 < a_2 < \dots < a_n \le 10^9$；
• $1 \le p_i \le 10^4$，$1 \le K \le 10^4$。

各测试点的约束如下：

• 特殊性质 A：所有任务的页数都小于 $K$，即 $p_i < K$。