\begin{problem}{Банк}{bank.in}{bank.out}{2 секунды}{256 мегабайт}

%Автор задачи: Виталий Аксенов
%Автор условия: Виталий Аксенов

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

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

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

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

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

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

\InputFile
В первой строке заданы два целых числа $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$,
                                                               
\OutputFile
Выведите $n$ целых чисел, $i$-е число должно быть равно числу минут после открытия,
когда $i$-й гном покинет банк.

\Examples

\begin{example}%
\exmp{
4 2
1 3 3
1 2 2
2 2 1
2 1 4
}{
8
5
9
13
}%
\end{example}

\end{problem}
