19785번 - Банк 다국어

문제

В одном далеком мире, в славном городе Эрбовле открыли новый банк. В банке есть $m$ сотрудников, работающих с клиентами, и один главный бухгалтер.

Для решения своих проблем в банк приходят гномы. Известно, что $i$-й гном приходит в банк через $t_i$ минут после открытия банка. Сначала ему нужно провести $a_i$ минут у одного из $m$ сотрудников, а потом еще $b_i$ минут в офисе главного бухгалтера.

Разумеется несколько гномов не могут одновременно находиться у одного сотрудника или в офисе главного бухгалтера, поэтому к сотрудникам и к главному бухгалтеру формируются очереди.

Очередь к сотрудникам общая, при этом гном из очереди идет к первому освободившемуся сотруднику. Если в банк одновременно приходят два гнома, то первым в очередь к сотрудникам встает тот, чей номер меньше. Если гном начал обслуживаться у сотрудника в момент $x,ドル то он освобождается в момент $x+a_i,ドル в этот момент другой гном может начать обслуживаться у этого же сотрудника. Гном, пришедший в банк в момент $t,ドル может начать обслуживаться у сотрудника в любой момент, начиная с $t$.

Решив свои проблемы у сотрудника, гном идет в очередь к главному бухгалтеру. Аналогично, если два гнома приходят в эту очередь одновременно, первым встает гном с меньшим номером, в момент, когда заканчивается обслуживание одного из гномов, может сразу начаться обслуживание следующего, гном может попасть к главному бухгалтеру, начиная с того момента, когда закончил обслуживаться у сотрудника.

Сегодня в банк собирается прийти $n$ гномов, про каждого известно: во сколько он заходит в банк, сколько времени он хочет провести у окошка и сколько времени он хочет провести у бухгалтера. Нужно сообщить время выхода из банка для каждого гнома.

입력

В первой строке заданы два целых числа $n$ и $m$ (1ドル \le n \le 100,000円,ドル 1ドル \le m \le 10$) --- число гномов и сотрудников, соответственно. Далее, в $n$ строках задано по три целых числа $t_i,ドル $a_i$ и $b_i$ (1ドル \le t_i, a_i, b_i \le 10^9$) --- время прихода $i$-го гнома, сколько минут $i$-й гном должен провести у сотрудника банка и сколько минут он должен провести в офисе главного бухгалтера. Известно, что гномы заданы в порядке прихода в банк, то есть для любой пары $i < j$ выполняется $t_i \le t_j,ドル

출력

Выведите $n$ целых чисел, $i$-е число должно быть равно числу минут после открытия, когда $i$-й гном покинет банк.

제한

힌트