Bank
Uzaq bir dünyada, məşhur Erbovli şəhərində yeni bir bank açılıb. Bu bankda müştərilərlə işləyən m əməkdaş və bir baş mühasib fəaliyyət göstərir.
Bankın problemlərini həll etmək üçün cırtdanlar bura gəlir. Məlumdur ki, i-ci cırtdan bank açıldıqdan t_i dəqiqə sonra gəlir. İlk olaraq, o, m əməkdaşdan birində a_i dəqiqə vaxt keçirməlidir, daha sonra isə baş mühasibin ofisində b_i dəqiqə vaxt keçirməlidir.
Aydındır ki, eyni anda bir neçə cırtdan eyni əməkdaşda və ya baş mühasibin ofisində ola bilməz, buna görə də əməkdaşlar və baş mühasib üçün növbələr yaranır.
Əməkdaşlar üçün növbə ümumidir, yəni növbədəki cırtdan boşalan ilk əməkdaşa yönləndirilir. Əgər eyni anda iki cırtdan banka gəlirsə, növbədə birinci olan cırtdan nömrəsi kiçik olandır. Əgər cırtdan x anında əməkdaşda xidmətə başlayırsa, x+a_i anında azad olur və bu anda başqa bir cırtdan həmin əməkdaşda xidmətə başlaya bilər. Banka t anında gələn cırtdan, t anından başlayaraq istənilən anda əməkdaşda xidmətə başlaya bilər.
Əməkdaşda problemlərini həll etdikdən sonra cırtdan baş mühasibin növbəsinə keçir. Eyni qaydada, əgər iki cırtdan eyni anda bu növbəyə gəlirsə, birinci olan cırtdan nömrəsi kiçik olandır. Bir cırtdanın xidməti bitdikdə, dərhal növbəti cırtdanın xidməti başlaya bilər. Cırtdan əməkdaşda xidməti bitirdiyi andan başlayaraq baş mühasibə gedə bilər.
Bu gün banka n cırtdan gələcək və hər biri haqqında məlumdur: banka nə vaxt daxil olur, əməkdaşda nə qədər vaxt keçirmək istəyir və mühasibdə nə qədər vaxt keçirmək istəyir. Hər cırtdanın bankdan çıxış vaxtını bildirmək lazımdır.
Giriş verilənləri
Birinci sətirdə iki tam ədəd n və m (1 ≤ n ≤ 100000, 1 ≤ m ≤ 10) — cırtdanların və əməkdaşların sayı verilir. Sonra, n sətirdə üç tam ədəd t_i, a_i və b_i (1 ≤ t_i, a_i, b_i ≤ 10^9) — i-ci cırtdanın gəlmə vaxtı, i-ci cırtdanın bank əməkdaşında nə qədər dəqiqə keçirməli olduğu və baş mühasibin ofisində nə qədər dəqiqə keçirməli olduğu verilir. Məlumdur ki, cırtdanlar banka gəlmə sırasına görə verilir, yəni istənilən i < j cütü üçün t_i ≤ t_j şərti ödənilir.
Çıxış verilənləri
n tam ədəd çıxarın, i-ci ədəd bank açıldıqdan sonra i-ci cırtdanın bankı tərk etdiyi dəqiqə sayına bərabər olmalıdır.