问题描述

有一家餐厅最多可以同时容纳 K 名顾客。在这家餐厅前有一条侧街，那里有一个排队系统。

在时间 0 时，餐厅内没有顾客，队列为空。

今天，有 N 组顾客计划到来，他们按到达顺序编号从 1 到 N 。第 i 组有 Ci​ 人，在时间 Ai​ 加入队伍的末尾，并在进入后经过 Bi​ 时间单位离开餐厅。

每一组顾客在同时满足以下两个条件时，最早离开队列进入餐厅：

• 该组位于队列的最前面。换句话说，在那一刻仍然在队列中的组中，该组是最早加入的。
• 当将该组的人数与当前在餐厅中的所有组的人数相加时（包括正好在该时刻进入的人数，不包括离开的人数），总人数为 K 或更少。

找出每个组进入餐厅的时间。

约束条件

• 1≤N≤3×105
• 1≤K≤107
• 1≤Ai​,Bi​≤107 (1≤i≤N)
• A1​<⋯<AN​
• 1≤Ci​≤K (1≤i≤N)
• 所有输入值都是整数。

示例输入 1 复制

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

示例输出 1 复制

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 。

样本输入 2 复制

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

样本输出 2 复制

30
330
330
330

每个小组的进入和离开按以下方式进行：

• 在时间 30 时，小组 1 加入队列并立即进入，使得餐厅中的顾客数量为 10 。
• 在时间 60 时，小组 2 加入队列。
• 在时间 90 时，组 3 加入队列。
• 在时间 120 时，组 4 加入队列。
• 在时间 330 时，组 1 离开，使餐厅中的顾客数量为 0 。紧接着，组 2,3,4 进入，使餐厅中的顾客数量为 9 。
• 在时间 375 时，组 2,3,4 离开，使餐厅中的顾客数量为 0 。

示例输入 3Copy

10 24
279290 9485601 1
1094410 8022270 4
1314176 7214745 5
1897674 5924694 10
1921802 5769841 4
2506394 2765234 2
2558629 2727489 9
2681289 4061363 5
3022540 2291905 3
4407692 1313036 8

Sample Output 3

279290
1094410
1314176
1897674
1921802
7691643
7822368
8528921
8528921
10549857