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