주차장 대기열

문제

한 주차장에는 1번부터 K번까지 번호가 붙은 주차 칸이 K개 있다. 차량 N대가 도착하는 기록이 도착 시각 순으로 주어진다. i번째 차량은 시각 t_i에 도착하고, 주차하면 정확히 s_i 시간 동안 머문 뒤 출발하며, 도착 후 p_i 시간까지만 기다릴 수 있다. 처리 규칙은 다음과 같다. 차량이 도착했을 때 빈 칸이 있으면 번호가 가장 작은 빈 칸에 즉시 주차한다. 빈 칸이 없으면 대기열의 맨 뒤에 선다. 대기열은 먼저 선 차량이 먼저 들어가는 선입선출이다. 시각 T에 어떤 칸이 비면, 그 시각에 아직 대기 중인 차량 중 대기열 맨 앞 차량이 그 칸에 즉시 주차한다. 차량은 시각 t_i + p_i 이하에 주차를 시작하지 못하면 그 시각이 지나는 순간 대기열을 떠나고, 더는 들어오지 않는다. 즉 시각 t_i + p_i 에 정확히 칸이 비는 경우에는 주차할 수 있다. 같은 시각에 출발과 도착이 겹치면 출발을 먼저 처리한다. 같은 시각에 여러 칸이 비면 번호가 작은 칸부터 대기열 앞 차량에게 배정된다. s_i가 1 이상이므로 주차를 시작한 시각과 출발 시각은 다르다. 각 차량이 주차한 칸 번호와 주차를 시작한 시각을 구한다. 끝내 주차하지 못한 차량은 -1을 출력한다.

입력

첫 줄에 K와 N이 공백으로 주어진다 (1 ≤ K ≤ 100,000, 1 ≤ N ≤ 15,000). 이어서 N개의 줄에 t_i s_i p_i 가 주어진다 (0 ≤ t_i ≤ 10^9, 1 ≤ s_i ≤ 10^9, 0 ≤ p_i ≤ 10^9). t_1 ≤ t_2 ≤ ... ≤ t_N 이다. 모든 값은 정수이다.

출력

i번째 줄에 i번째 차량이 주차한 칸 번호와 주차 시작 시각을 공백으로 구분해 출력한다. 주차하지 못했다면 -1 한 개만 출력한다.

2 5
0 5 3
1 5 3
2 2 5
3 1 1
4 1 10

1 0
2 1
1 5
-1
2 6

1 3
0 2 0
2 1 0
2 1 0

1 0
1 2
-1

출처: Devin.KR 자체 제작