题目描述

有一家餐厅同时容纳的顾客人数最多为 $K$。餐厅门前有一条侧路，排着一条队列。

初始时刻 $0$，餐厅里没有顾客，队列也为空。

今天会按到达时间依次来 $N$ 组顾客，编号为 $1$ 到 $N$。第 $i$ 组有 $C_i$ 人，于时间 $A_i$ 到达并加入队列尾部，且在进入餐厅后会停留 $B_i$ 个时间单位后离开。

每一组进入餐厅的规则为：当且仅当以下两条同时满足时，该组会在最早的时刻离开队列并进入餐厅：

• 该组位于队首（即在当前队列中是最早加入的仍在队列中的组）；
• 若把该组的人数与此刻已在餐厅中的所有组的人数（包含在该时刻同时进入但不包含同时离开的）相加，人数不超过 $K$。

请你求出每一组进入餐厅的时间。

输入格式

输入共 $N+1$ 行；

• 第 $1$ 行输入两个正整数 $N, K$，由空格隔开。
• 随后输入 $N$ 行，第 $i + 1$ $（1 \le i \le N）$ 行输入三个正整数 $A_i, B_i, C_i$，由空格隔开。

输出格式

输出 $N$ 行，第 $i$ 行（$1\le i\le N$）应当包含第 $i$ 组进入餐厅的时间（整数）。

样例输入 1

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

样例输出 1

30
60
105
120

样例输入 2

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

样例输出 2

30
330
330
330

样例输入 3

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

样例输出 3

279290
1094410
1314176
1897674
1921802
7691643
7822368
8528921
8528921
10549857

说明

样例 1 解释

• 时刻 $30$，第 $1$ 组到达并加入队列，立刻进入，餐厅内人数变为 $3$。
• 时刻 $60$，第 $2$ 组到达并立即进入，餐厅内人数变为 $7$。
• 时刻 $90$，第 $3$ 组到达并加入队列（无法立即进入）。
• 时刻 $105$，第 $2$ 组离开，使餐厅内人数降为 $3$，此时第 $3$ 组成为队首并且可以进入，餐厅人数变为 $8$。
• 时刻 $120$，第 $4$ 组到达并立即进入，餐厅人数变为 $10$。
• 随后各组按其停留时间陆续离开。

样例 2 解释

• 时刻 $30$，第 $1$ 组到达并进入，餐厅人数为 $10$（已满）。
• 时刻 $60,90,120$，第 $2,3,4$ 组依次到达加入队列，但均不能进入。
• 时刻 $330$，第 $1$ 组离开，餐厅人数为 $0$，随后队列中的第 $2,3,4$ 组立即按队首顺序进入（同时进入允许），餐厅人数为 $2+3+4=9$。
• 各组在各自停留结束时离开。

数据范围

• $1\le N\le 3\times 10^5$；
• $1\le K\le 10^7$；
• $1\le A_i,B_i\le 10^7$ 对所有 $1\le i\le N$ 成立；
• $A_1< A_2<\cdots< A_N$（到达时间严格递增）；
• $1\le C_i\le K$ 对所有 $i$ 成立；
• 所有输入值均为整数。