AT_abc423_d [ABC423D] Long Waiting

There is a restaurant that can accommodate at most $ K $ customers simultaneously. In front of this restaurant, there is a side street where one queue is managed. At time $ 0 $ , there are no customers in the restaurant, and the queue is also empty. Today, $ N $ groups of customers are scheduled to come, and they are numbered from $ 1 $ to $ N $ in the order of their arrival. Group $ i $ consists of $ C_i $ people, joins the end of the queue at time $ A_i $ , and leaves the restaurant $ B_i $ time units after entering. Each group enters the restaurant by leaving the queue at the earliest time when both of the following two conditions are satisfied simultaneously: - The group is at the front of the queue. In other words, the group is the earliest to have joined among those still in the queue at that point. - When the number of people in that group and all groups currently in the restaurant (including those entering at exactly that time and excluding those leaving) are combined, there are $ K $ or fewer people. Find the time when each group enters the restaurant.

The input is given from Standard Input in the following format: > $ N $ $ K $ $ A_1 $ $ B_1 $ $ C_1 $ $ \vdots $ $ A_N $ $ B_N $ $ C_N $

Output $ N $ lines. The $ i $ -th line ( $ 1 \leq i \leq N $ ) should contain the time when group $ i $ enters the restaurant as an integer.

### Sample Explanation 1 The entry and exit of each group proceed as follows: - At time $ 30 $ , group $ 1 $ joins the queue and immediately enters, making the number of customers in the restaurant $ 3 $ . - At time $ 60 $ , group $ 2 $ joins the queue and immediately enters, making the number of customers in the restaurant $ 7 $ . - At time $ 90 $ , group $ 3 $ joins the queue. - At time $ 105 $ , group $ 2 $ leaves, making the number of customers in the restaurant $ 3 $ . Immediately after, group $ 3 $ enters, making the number of customers in the restaurant $ 8 $ . - At time $ 120 $ , group $ 4 $ joins the queue and immediately enters, making the number of customers in the restaurant $ 10 $ . - At time $ 150 $ , group $ 3 $ leaves, making the number of customers in the restaurant $ 5 $ . - At time $ 165 $ , group $ 4 $ leaves, making the number of customers in the restaurant $ 3 $ . - At time $ 330 $ , group $ 1 $ leaves, making the number of customers in the restaurant $ 0 $ . ### Sample Explanation 2 The entry and exit of each group proceed as follows: - At time $ 30 $ , group $ 1 $ joins the queue and immediately enters, making the number of customers in the restaurant $ 10 $ . - At time $ 60 $ , group $ 2 $ joins the queue. - At time $ 90 $ , group $ 3 $ joins the queue. - At time $ 120 $ , group $ 4 $ joins the queue. - At time $ 330 $ , group $ 1 $ leaves, making the number of customers in the restaurant $ 0 $ . Immediately after, groups $ 2,3,4 $ enter, making the number of customers in the restaurant $ 9 $ . - At time $ 375 $ , groups $ 2,3,4 $ leave, making the number of customers in the restaurant $ 0 $ . ### Constraints - $ 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 $ ) - All input values are integers.