우체국 창구 배정

문제

어느 우체국에는 1번부터 M번까지 번호가 붙은 M개의 창구가 있다. 오늘 N명의 손님이 오며, i번째 손님은 시각 t_i 에 도착하고 업무를 보는 데 s_i 만큼의 시간이 걸린다. 손님은 입력 순서대로 도착하며 도착 시각은 줄어들지 않는다. 같은 시각에 도착한 손님은 입력 순서대로 줄을 선다. 손님은 한 줄로 서서 기다리며, 앞사람이 먼저 창구에 배정된다. 어떤 손님이 창구에 배정될 수 있는 가장 이른 시각은 그 손님이 도착한 시각과 어떤 창구가 비는 가장 이른 시각 중 큰 값이다. 창구는 업무가 끝나는 시각에 곧바로 비는 것으로 본다. 배정 시각에 비어 있는 창구가 여러 개이면 번호가 가장 작은 창구를 쓴다. 단, 도착 후 기다리는 중에 비게 된 창구라면 손님이 배정되는 시각에 비어 있는 창구들 중에서 번호가 가장 작은 것을 고른다. 아직 쓰지 않은 창구는 시각 0부터 비어 있다. 우체국은 시각 T 에 문을 닫는다. 어떤 손님이 창구에 배정되는 시각이 T 이상이면 그 손님은 업무를 보지 못하고 돌아가며, 어떤 창구도 차지하지 않는다. 시작한 업무는 T 를 넘겨도 끝까지 진행한다. 각 손님에 대해 배정된 창구 번호와 업무가 끝나는 시각을 구하고, 돌아간 손님은 -1 을 출력하라. 마지막에는 업무를 본 손님의 수도 출력한다.

입력

첫째 줄에 N, M, T(1 ≤ N ≤ 200,000, 1 ≤ M ≤ 200,000, 1 ≤ T ≤ 10^9)가 주어진다. 이어지는 N개의 줄에 i번째 손님의 t_i 와 s_i(0 ≤ t_i ≤ 10^9, 1 ≤ s_i ≤ 10^6)가 주어진다. t_1 ≤ t_2 ≤ ... ≤ t_N 이다. 모든 값은 정수이다.

출력

N개의 줄에 i번째 손님의 결과를 출력한다. 업무를 본 손님이면 `창구번호 끝나는시각`을 공백으로 구분해 출력하고, 돌아간 손님이면 -1 을 출력한다. 마지막 줄에 업무를 본 손님의 수를 출력한다.

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

1 4
2 4
1 6
2 9
-1
4

3 1 5
0 5
0 1
4 1

1 5
-1
-1
1

3 3 100
5 10
5 10
20 1

1 15
2 15
1 21
3

출처: Devin.KR 자체 제작