가장 빠른 추가 진료 예약

문제

병원의 예약 관리 담당자는 한 진료실에 추가 예약 한 건을 배정하려 한다. 예약을 검토할 기간은 기준 날짜의 00시 00분부터 정확히 H분 동안이다. 기간 중에는 매일 같은 시간 기준을 사용하며, 야간이나 휴일이라는 이유로 진료를 중단하지 않는다. 모든 예약은 분 단위 시각에 시작하고 끝난다. 이미 등록된 예약은 N건이며, 각 예약의 진료 시간은 모두 D분이다. 기존 예약의 시작 시각 t_i는 기준 날짜의 00시 00분에서 몇 분이 지났는지를 나타내는 정수로 주어진다. 해당 예약은 t_i분 시점부터 t_i+D분 시점 직전까지 진료실을 사용한다. 입력에는 여러 경로에서 중복 수집된 예약이 들어 있을 수 있으므로 시작 시각이 같거나 사용 시간이 겹치는 예약도 허용한다. 겹치는 예약이 있으면 그 시간 전체를 사용 중인 것으로 취급한다. 추가하려는 예약의 진료 시간은 L분이다. 시작 시각을 s라고 하면 s부터 s+L 직전까지의 모든 시간이 기존 예약의 사용 시간과 겹치지 않아야 한다. 또한 추가 예약의 시작과 종료가 모두 검토 기간 안에 있어야 하므로 0 ≤ s이고 s+L ≤ H여야 한다. 기존 예약이 끝나는 바로 그 시각에 추가 예약을 시작하거나, 추가 예약이 끝나는 바로 그 시각에 기존 예약이 시작하는 것은 허용한다. 담당자는 가능한 시작 시각 중 가장 빠른 것을 선택한다. 가능한 시각이 없으면 -1을 출력한다. 기존 예약이 한 건도 없는 경우도 있으며, 이때에도 같은 기간 제한을 적용한다. 가능한 시각이 있으면 기준 날짜에 s분을 더한 날짜와 시각을 출력한다. 날짜는 그레고리력을 따른다. 연도가 400의 배수이거나, 4의 배수이면서 100의 배수가 아니면 윤년이다. 윤년의 2월은 29일까지이고 그 밖의 해에는 28일까지이다. 시간대 변경과 윤초는 없으며 하루는 항상 1,440분이다.

입력

첫째 줄에 유효한 기준 날짜가 YYYY-MM-DD 형식으로 주어진다. 기준 날짜의 연도는 2000 이상 2090 이하이다.
둘째 줄에 정수 H, D, L, N이 공백으로 구분되어 주어진다.
이후 N개의 줄에 기존 예약의 시작 시각 t_i가 하나씩 주어진다. N이 0이면 이후 줄은 없다.
1 ≤ H ≤ 525,600
1 ≤ D ≤ H
1 ≤ L ≤ H
0 ≤ N ≤ 100,000
0 ≤ t_i ≤ H-D
모든 수치 입력값은 정수이며 예약은 시작 시각순으로 주어진다는 보장이 없다.

출력

추가 예약이 가능하면 가장 빠른 시작 시각을 YYYY-MM-DD HH:MM 형식으로 출력한다. 월, 일, 시, 분은 각각 두 자리로 출력하며 시는 00부터 23까지이다. 추가 예약이 불가능하면 -1만 출력한다.

2028-02-28
3000 60 90 3
0
100
1500

2028-02-28 02:40

2028-02-28
3000 1440 60 1
0

2028-02-29 00:00

2026-10-24
120 45 40 2
0
70

-1

출처: Devin.KR 자체 제작