Банк
У одному далекому світі, у славному місті Ербовлі відкрили новий банк. У банкі є m співробітників, які працюють з клієнтами, і один головний бухгалтер.
Для вирішення своїх проблем до банку приходять гноми. Відомо, що i-й гном приходить до банку через t_i хвилин після відкриття банку. Спочатку йому потрібно провести a_i хвилин у одного з m співробітників, а потім ще b_i хвилин у офісі головного бухгалтера.
Зрозуміло, що декілька гномів не можуть одночасно знаходитись у одного співробітника або в офісі головного бухгалтера, тому до співробітників та до головного бухгалтера формуються черги.
Черга до співробітників спільна, при цьому гном з черги йде до першого співробітника, що звільнився. Якщо у банк одночасно приходять два гноми, то першим у чергу до співробітників стає той, чий номер менший. Якщо гном розпочав обслуговуватись у співробітника у момент x, то він звільняється у момент x+a_i, у цей момент інший гном може почати обслуговуватись у цього ж співробітника. Гном, який прийшов до банку у момент t, може почати обслуговуватись у співробітника у довільний момент, починаючи з t.
Вирішивши свої проблеми у співробітника, гном йде у чергу до головного бухгалтера. Аналогічно, якщо два гноми приходять у цю чергу одночасно, першим стає гном з меншим номером, у момент, коли завершується обслуговування одного з гномів, може відразу початись обслуговування наступного, гном може потрапити до головного бухгалтера, починаючи з того моменту, коли завершив обслуговуватись у співробітника.
Сьогодні до банку збирається прийти n гномів, про кожного відомо: у скільки він заходить до банку, скільки часу він хоче провести у віконця і скільки вчасу він хоче провести у бухгалтера. Потрібно повіомити час виходу з банку для кожного гнома.
Вхідні дані
У першому рядку задано два цілих числа n та m (1 ≤ n ≤ 100000, 1 ≤ m ≤ 10) — число гномів та співробітників, відповідно. Далі, у n рядках задано по три цілих числа t_i, a_i та b_i (1 ≤ t_i, a_i, b_i ≤ 10^9) — час приходу i-го гнома, скільки хвилин i-й гном повинен провести у співробітника банку і скільки хвилин він повинен провести в офісі головного бухгалтера. Відомо, що гномів задано у порядку приходу до банку, тобто для довільної пари i < j виконується t_i ≤ t_j.
Вихідні дані
Виведіть n цілих чисел, i-те число повинно бути рівним числу хвилин після відкриття, колиа i-й гном покине банк.