题目描述

有一家餐厅最多能同时容纳K名顾客。餐厅前有一条小巷，管理着一个队列。 在时间$0$，餐厅内没有顾客，队列也为空。 今天，预计有$N$组顾客到来，按到达顺序编号为$1$到$N$。第$i$组由$C_i$人组成，在时间$A_i$加入队列末尾，并在进入餐厅$B_i$个单位时间后离开。

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

1. 该组位于队列的最前面。即，在此时仍在队列中的所有组中，该组是最早加入的。
2. 当该组的人数与当前餐厅内所有组（包括恰好此时进入的组，不包括此时离开的组）的人数之和不超过K人。

求每组顾客进入餐厅的时间。

输入格式

$N$ $K$

$A_1$ $B_1$ $C_1$

⋮

$A_N$ $B_N$ $C_N$

输出格式

输出N行。第i行（1≤i≤N）应包含第i组进入餐厅的时间（整数）。

数据范围

$1 \leq N \leq 3e5.$

$1 \leq K \leq 1e7.$

$1 \leq A_i,B_i \leq 1e7.$ (1≤i≤N)

$$A_i$\leq ... \leq$ $A_N$.

$1 \leq C_i \leq K.$ (1≤i≤N)

输入样例:

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

输出样例：

30
60
105
120