휴게 시간을 지키는 예약실

문제

한 병원 예약실에는 진료실이 하나 있다. 하루의 시각은 기준 시각부터 지난 분을 나타내는 음이 아닌 정수로 표현한다. 예약실에는 N명의 환자가 도착하며, 각 환자의 도착 시각과 필요한 진료 시간이 미리 주어진다. 환자는 도착 시각이 빠른 순서로 검토하고, 도착 시각이 같으면 입력에 먼저 나온 환자부터 검토한다. 환자의 번호는 입력에 나온 순서대로 1번부터 N번까지다. 진료실은 시각 0부터 사용할 수 있다. 한 환자의 진료가 끝나면 C분 동안 정리해야 다음 환자의 진료를 시작할 수 있다. 정리는 휴게 시간과 겹쳐 진행할 수 있다. 병원은 시각 L부터 R 직전까지 휴게 시간을 가지며, 진료는 휴게 시간과 조금이라도 겹칠 수 없다. 시작 시각이 s이고 진료 시간이 d이면 진료 구간은 s 이상 s+d 미만이다. 따라서 L에 끝나는 진료와 R에 시작하는 진료는 허용된다. 각 환자를 검토할 때, 앞서 확정한 진료와 정리를 모두 마쳤고 해당 환자가 도착한 뒤인 시각 중 가장 이른 진료 시작 시각을 먼저 구한다. 그 시각에 시작하면 휴게 시간과 겹치는 경우에는 시작 시각을 R로 늦춘다. 이렇게 구한 시작 시각과 환자의 도착 시각의 차이가 W 이하이면 예약을 확정한다. 차이가 W보다 크면 그 환자는 예약하지 않고 떠난다. 예약하지 않은 환자는 진료실을 사용하지 않으며 정리 시간도 발생시키지 않는다. 이전에 확정한 예약을 취소하거나 다른 환자와 순서를 바꾸지 않는다. 휴게 시간 이후에는 진료 종료 시각에 별도의 상한이 없다. 모든 환자를 검토한 결과를 구하는 프로그램을 작성한다. 각 환자에게 확정된 시작 시각을 알려 주고, 예약하지 않은 환자는 -1로 표시한다.

입력

첫째 줄에 정수 N, C, W, L, R이 주어진다. 1 ≤ N ≤ 20,000, 0 ≤ C ≤ 30, 0 ≤ W ≤ 1,000,000, 0 ≤ L < R ≤ 1,000,000이다.
다음 N개 줄에 환자의 도착 시각 A_i와 진료 시간 D_i가 주어진다. 모두 정수이며 0 ≤ A_i ≤ 1,000,000, 1 ≤ D_i ≤ 30이다. 도착 시각은 감소하지 않는 순서로 주어진다.

출력

N개의 줄을 출력한다. i번째 줄에 i번 환자의 진료 시작 시각을 출력한다. 해당 환자가 예약하지 않았다면 -1을 출력한다.

5 2 4 10 15
0 4
3 3
8 3
9 1
15 2

0
6
-1
-1
15

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

3
-1
9
-1

출처: Devin.KR 자체 제작