该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

有一家餐厅，最多能同时容纳 $K$ 位顾客。餐厅门口有条小巷，排着一条队。

在时间点 $0$，餐厅里没人，队伍也空空如也。

今天预计会有 $N$ 组客人来访，他们按到达顺序编号从 $1$ 到 $N$。第 $i$ 组有 $C_i$ 个人，他们在时间 $A_i$ 加入队尾，进入餐厅后 $B_i$ 时间单位离开。

每组客人何时能进餐厅，取决于以下两个条件同时满足的最早时刻：

• 该组排在队伍最前面，也就是说，在队伍中他们是最早加入的。

• 这组人数加上餐厅里当前所有顾客（包括刚好在那时进入的，排除刚离开的）总数不超过 $K$ 人。

请你算出每组客人进入餐厅的具体时间。

约束条件

$1 ≤ N ≤ 3 × 10^5$

$1 ≤ K ≤ 10^7$

$1 ≤ A_i, B_i ≤ 10^7 (1 ≤ i ≤ N)$

$A_1 < ⋯ < A_N$

$1 ≤ C_i ≤ K (1 ≤ i ≤ N)$

所有输入数值均为整数。

输入格式

输入从标准输入读取，格式如下：

输出格式

输出 $N$ 行，第 $i$ 行$（1 ≤ i ≤ N）$应输出第 $i$ 组客人进入餐厅的时间，整数形式。

样例

4 10
30 300 3
60 45 4
90 45 5
120 45 2

30
60
105
120

样例解释

时间30，第1组加入队伍，马上进入餐厅，餐厅内人数变为3。

时间60，第2组加入队伍，立刻进入，餐厅人数变为7。

时间90，第3组加入队伍。

时间105，第2组离开，餐厅人数变为3。紧接着第3组进入，餐厅人数变为8。

时间120，第4组加入队伍，马上进入，餐厅人数变为10。

时间150，第3组离开，餐厅人数变为5。

时间165，第4组离开，餐厅人数变为3。

时间330，第1组离开，餐厅人数变为0。