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 翻译