AT_abc423_d [ABC423D] Long Waiting

同時に最大 $ K $ 人の客を入れられるレストラン店があります。この店の前には脇道があり、ここで $ 1 $ つの待ち行列を管理しています。 時刻 $ 0 $ の時点で店内に客はおらず、待ち行列も空です。 今日は $ N $ 個の団体客が来る予定であり、来訪が早い順に $ 1 $ から $ N $ までの番号が付けられています。団体客 $ i $ の人数は $ C_i $ 人で、時刻 $ A_i $ に待ち行列の末尾に加わります。また、この団体客は入店してから $ B_i $ 単位時間後に退店します。 それぞれの団体客は、以下の $ 2 $ 条件が同時に満たされた最も早い時刻に、待ち行列を離れて入店します。 - その団体客は、待ち行列の先頭にいる。つまりその団体客は、その時点で待ち行列にいる団体客のうち、最も早く待ち行列に加わっている。 - その団体客と、店内にいるすべての団体客 (ちょうどその時刻に入店したぶんを含み、退店したぶんを除く) の人数を合算すると、 $ K $ 人以下になる。 それぞれの団体客が入店する時刻を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ K $ $ A_1 $ $ B_1 $ $ C_1 $ $ \vdots $ $ A_N $ $ B_N $ $ C_N $

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

### Sample Explanation 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 $ 名になる。 ### Sample Explanation 2 各団体客の入退店は以下の流れで進みます。 - 時刻 $ 30 $ に、団体客 $ 1 $ が待ち行列に加わった直後にそのまま入店し、店内の客は $ 10 $ 名になる。 - 時刻 $ 60 $ に、団体客 $ 2 $ が待ち行列に加わる。 - 時刻 $ 90 $ に、団体客 $ 3 $ が待ち行列に加わる。 - 時刻 $ 120 $ に、団体客 $ 4 $ が待ち行列に加わる。 - 時刻 $ 330 $ に、団体客 $ 1 $ が退店し、店内の客は $ 0 $ 名になる。その直後、団体客 $ 2,3,4 $ が入店し、店内の客は $ 9 $ 名になる。 - 時刻 $ 375 $ に、団体客 $ 2,3,4 $ が退店し、店内の客は $ 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 $ ) - 入力される値はすべて整数