상담 창구 배정

문제

고객센터에 1번부터 K번까지 상담 창구가 있다. 손님 N명이 도착한 순서대로 주어진다. i번째 손님은 시각 t_i 에 도착하고 상담에 s_i 분이 걸린다. - 손님이 도착했을 때 비어 있는 창구가 있으면 그중 번호가 가장 작은 창구에서 바로 상담을 시작한다. 도착한 시각에 상담이 끝나는 창구도 비어 있는 것으로 본다. - 비어 있는 창구가 없으면 줄을 선다. 줄은 먼저 온 손님부터 나간다. 줄 맨 앞 손님은 가장 먼저 비는 창구로 가고, 같은 시각에 여러 창구가 비면 번호가 가장 작은 창구로 간다. - 창구를 옮겨 다니는 시간은 없다. 손님마다 몇 번 창구에서 언제 상담을 시작하는지 구하라.

입력

첫째 줄에 손님 수 N 과 창구 수 K 가 주어진다. (1 ≤ N ≤ 30,000, 1 ≤ K ≤ 100,000)

다음 N개 줄에 t_i 와 s_i 가 주어진다. (0 ≤ t_i ≤ 1,000,000, 1 ≤ s_i ≤ 10,000) t_i 는 줄어들지 않는다.

출력

손님마다 한 줄에 창구 번호와 상담 시작 시각을 공백으로 구분해 입력 순서대로 출력한다.

5 2
0 5
1 3
2 4
4 2
9 1

1 0
2 1
2 4
1 5
1 9

3 3
0 10
0 10
10 1

1 0
2 0
1 10

출처: Devin.KR 자체 제작