Задача C. Банк ≡

Условие

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

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

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

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

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

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

Формат входного файла

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

Формат выходного файла

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

Примеры тестов

4 2
1 3 3
1 2 2
2 2 1
2 1 4

8
5
9
13