В одном далеком мире, в славном городе Эрбовле открыли новый банк. В банке есть \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}-й гном покинет банк.