D - Long Waiting Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

同時に最大 K 人の客を入れられるレストラン店があります。この店の前には脇道があり、ここで 1 つの待ち行列を管理しています。

時刻 0 の時点で店内に客はおらず、待ち行列も空です。

今日は N 個の団体客が来る予定であり、来訪が早い順に 1 から N までの番号が付けられています。団体客 i の人数は C_i 人で、時刻 A_i に待ち行列の末尾に加わります。また、この団体客は入店してから B_i 単位時間後に退店します。

それぞれの団体客は、以下の 2 条件が同時に満たされた最も早い時刻に、待ち行列を離れて入店します。

  • その団体客は、待ち行列の先頭にいる。つまりその団体客は、その時点で待ち行列にいる団体客のうち、最も早く待ち行列に加わっている。
  • その団体客と、店内にいるすべての団体客 (ちょうどその時刻に入店したぶんを含み、退店したぶんを除く) の人数を合算すると、K 人以下になる。

それぞれの団体客が入店する時刻を求めてください。

制約

  • 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)
  • 入力される値はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

N K
A_1 B_1 C_1
\vdots
A_N B_N C_N

出力

N 行出力せよ。i 行目 (1 \leq i \leq N) には、団体客 i が入店する時刻を整数で出力せよ。

入力例 1

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

出力例 1

30
60
105
120

各団体客の入退店は以下の流れで進みます。

  • 時刻 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

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

出力例 2

30
330
330
330

各団体客の入退店は以下の流れで進みます。

  • 時刻 30 に、団体客 1 が待ち行列に加わった直後にそのまま入店し、店内の客は 10 名になる。
  • 時刻 60 に、団体客 2 が待ち行列に加わる。
  • 時刻 90 に、団体客 3 が待ち行列に加わる。
  • 時刻 120 に、団体客 4 が待ち行列に加わる。
  • 時刻 330 に、団体客 1 が退店し、店内の客は 0 名になる。その直後、団体客 2,3,4 が入店し、店内の客は 9 名になる。
  • 時刻 375 に、団体客 2,3,4 が退店し、店内の客は 0 名になる。

入力例 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

Score : 400 points

Problem Statement

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.

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.

Input

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

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 Input 1

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

Sample Output 1

30
60
105
120

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 Input 2

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

Sample Output 2

30
330
330
330

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.

Sample Input 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

Sample Output 3

279290
1094410
1314176
1897674
1921802
7691643
7822368
8528921
8528921
10549857