Bank
In the distant city of Erbovli, a new bank has opened its doors. This bank employs m staff members who assist clients, along with a chief accountant.
Dwarves visit the bank to address their issues. The i-th dwarf arrives t_i minutes after the bank opens. Initially, the dwarf spends a_i minutes with one of the m employees, followed by b_i minutes with the chief accountant.
Only one dwarf can be assisted by an employee or the chief accountant at any given time, resulting in queues for both the employees and the chief accountant.
The queue for employees is shared, and the next available employee assists the first dwarf in line. If two dwarves arrive simultaneously, the dwarf with the smaller index number is served first. If a dwarf begins service with an employee at time x, they finish at x+a_i, allowing the next dwarf to be served. A dwarf arriving at time t can start being served by an employee from time t onwards.
Once a dwarf finishes with an employee, they join the queue for the chief accountant. Similarly, if two dwarves reach this queue at the same time, the dwarf with the smaller index number is served first. The next dwarf can be served immediately after the previous one finishes. A dwarf can proceed to the chief accountant as soon as they finish with the employee.
Today, n dwarves will visit the bank. For each dwarf, the arrival time, the duration needed with an employee, and the time required with the accountant are known. Your task is to determine the time each dwarf leaves the bank.
Input
The first line contains two integers n and m (1 ≤ n ≤ 100000, 1 ≤ m ≤ 10) — the number of dwarves and employees, respectively. The next n lines each contain three integers t_i, a_i, and b_i (1 ≤ t_i, a_i, b_i ≤ 10^9) — the arrival time of the i-th dwarf, the minutes required with an employee, and the minutes needed with the chief accountant. Dwarves are listed in the order of their arrival, ensuring t_i ≤ t_j for any i < j.
Output
Output n integers, where the i-th integer represents the number of minutes after opening when the i-th dwarf exits the bank.