Bank

In a distant world, a new bank has opened in the glorious city of Erbovle. The bank has $m$ employees who serve clients and one chief accountant.

Dwarves come to the bank to take care of their business. The $i$-th dwarf arrives at the bank $t_i$ minutes after it opens. First he must spend $a_i$ minutes with one of the $m$ employees, and then another $b_i$ minutes in the chief accountant's office.

Of course, several dwarves cannot be with the same employee or in the chief accountant's office at the same time, so queues form at the employees and at the chief accountant.

The queue for the employees is shared, and a dwarf from the queue goes to the first employee who becomes free. If two dwarves arrive at the bank at the same time, the one with the smaller index joins the employees' queue first. If a dwarf starts being served by an employee at time $x$, he finishes at time $x+a_i$, and at that time another dwarf may start being served by the same employee. A dwarf who arrives at the bank at time $t$ may start being served by an employee at any time from $t$ onward.

After finishing his business with an employee, the dwarf joins the queue for the chief accountant. Similarly, if two dwarves join this queue at the same time, the one with the smaller index goes first; when one dwarf's service ends, the next dwarf's service may start immediately; and a dwarf may go to the chief accountant from the moment he finishes being served by an employee.

Today $n$ dwarves are going to come to the bank. For each one, the time he enters the bank, how long he wants to spend at a window, and how long he wants to spend with the accountant are known. Report the time each dwarf leaves the bank.

The first line contains two integers $n$ and $m$ ($1 \le n \le 100\,000$, $1 \le m \le 10$), the number of dwarves and employees, respectively. The next $n$ lines contain three integers each: $t_i$, $a_i$, and $b_i$ ($1 \le t_i, a_i, b_i \le 10^9$), the arrival time of the $i$-th dwarf, the number of minutes the $i$-th dwarf must spend with a bank employee, and the number of minutes he must spend in the chief accountant's office. The dwarves are given in order of arrival at the bank, that is, for every pair $i < j$ we have $t_i \le t_j$.

Print $n$ integers; the $i$-th number must be the number of minutes after opening when the $i$-th dwarf leaves the bank.