은행

어느 먼 세계의 에르보블레라는 도시에 새 은행이 문을 열었다. 은행에는 고객을 응대하는 직원 $m$명과 수석 회계사 한 명이 있다.

드워프들이 볼일을 보러 은행에 온다. $i$번째 드워프는 은행이 문을 연 뒤 $t_i$분 후에 은행에 도착한다. 먼저 $m$명의 직원 중 한 명에게 $a_i$분 동안 볼일을 보고, 그다음 수석 회계사 사무실에서 $b_i$분을 더 보내야 한다.

여러 드워프가 같은 직원이나 수석 회계사 사무실에 동시에 있을 수 없으므로, 직원과 수석 회계사 앞에는 줄이 생긴다.

직원 앞의 줄은 하나이고, 줄에 있는 드워프는 가장 먼저 비는 직원에게 간다. 두 드워프가 같은 시각에 은행에 도착하면 번호가 작은 드워프가 직원 줄에 먼저 선다. 드워프가 시각 $x$에 직원에게 응대를 받기 시작하면 시각 $x+a_i$에 끝나고, 그 시각에 다른 드워프가 같은 직원에게 응대를 받기 시작할 수 있다. 시각 $t$에 은행에 온 드워프는 $t$ 이후의 어느 시각에든 직원에게 응대를 받기 시작할 수 있다.

직원에게 볼일을 마친 드워프는 수석 회계사 줄로 간다. 마찬가지로 두 드워프가 이 줄에 같은 시각에 도착하면 번호가 작은 드워프가 먼저 서고, 한 드워프의 응대가 끝나는 시각에 다음 드워프의 응대가 바로 시작될 수 있으며, 드워프는 직원에게 볼일을 마친 시각 이후에 수석 회계사에게 갈 수 있다.

오늘 은행에 드워프 $n$명이 오려고 한다. 각 드워프에 대해 은행에 들어오는 시각, 창구에서 보내려는 시간, 회계사에게 보내려는 시간이 주어진다. 각 드워프가 은행을 나서는 시각을 구하시오.

첫째 줄에 두 정수 $n$과 $m$이 주어진다 ($1 \le n \le 100\,000$, $1 \le m \le 10$). $n$은 드워프의 수, $m$은 직원의 수이다. 다음 $n$개 줄에 세 정수 $t_i$, $a_i$, $b_i$가 주어진다 ($1 \le t_i, a_i, b_i \le 10^9$). $t_i$는 $i$번째 드워프가 도착하는 시각, $a_i$는 $i$번째 드워프가 은행 직원에게 보내야 하는 시간(분), $b_i$는 수석 회계사 사무실에서 보내야 하는 시간(분)이다. 드워프는 은행에 도착하는 순서대로 주어지며, 즉 $i < j$인 모든 쌍에 대해 $t_i \le t_j$이다.

정수 $n$개를 출력한다. $i$번째 수는 $i$번째 드워프가 은행을 떠나는 시각, 즉 은행이 문을 연 뒤 지난 시간(분)이어야 한다.