AT_abc423_d [ABC423D] Long Waiting

有一家餐厅，最多可同时容纳 $K$ 位顾客。在餐厅门前有一条小街道，管理着一支队列。 在时间 $0$ 时，餐厅内没有顾客，队列也是空的。 今天共有 $N$ 个顾客团体将到来，按照到达的顺序被编号为 $1$ 到 $N$。第 $i$ 个团体有 $C_i$ 人，在时间 $A_i$ 加入队列末尾，并在进入餐厅后经过 $B_i$ 个时间单位离开。 每个团体只有在同时满足以下两个条件时，才能从队列前端进入餐厅，并离开队列： - 该团体在队列的最前面。即，该团体是此时仍在队列中的所有团体中最早加入队列的。 - 该团体与当前餐厅中所有团体（包括此刻一起进入的，不包括此刻离开的）的人数之和，不超过 $K$。 请你求出每个团体进入餐厅的时间。

输入从标准输入给出，格式如下： > $N$ $K$ > $A_1$ $B_1$ $C_1$ > $\vdots$ > $A_N$ $B_N$ $C_N$

输出 $N$ 行。第 $i$ 行（$1 \leq i \leq N$）应为第 $i$ 个团体进入餐厅的时间，输出为整数。

### 样例解释 1 各团体的进入与离开过程如下： - 在时间 $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 各团体的进入与离开过程如下： - 在时间 $30$，团体 $1$ 加入队列，立即入店，餐厅内人数为 $10$。 - 在时间 $60$，团体 $2$ 加入队列。 - 在时间 $90$，团体 $3$ 加入队列。 - 在时间 $120$，团体 $4$ 加入队列。 - 在时间 $330$，团体 $1$ 离开，餐厅人数为 $0$。此时团体 $2,3,4$ 紧接着进入，餐厅人数变为 $9$。 - 在时间 $375$，团体 $2,3,4$ 离开，餐厅人数为 $0$。 ### 数据范围 - $1 \leq N \leq 3 \times 10^5$ - $1 \leq K \leq 10^7$ - $1 \leq A_i, B_i \leq 10^7$（$1 \leq i \leq N$） - $A_1 < \dots < A_N$ - $1 \leq C_i \leq K$（$1 \leq i \leq N$） - 所有输入值均为整数。 由 ChatGPT 5 翻译