22235번 - 가희와 수인 분당선 1

하행은 서울을 시점으로 종점 방향으로 운행하는 방향을 의미합니다.

수인 분당선은 K209(청량리)역이 서울에 있고, K272(인천)역이 인천에 있으므로, K209역에서 K272역으로 가는 방향이 하행이 됩니다.

[그림 1] 수인 분당선의 하행

수인 분당선의 역 번호는 Kddd로 정의됩니다. 이 때 ddd는 209 이상 272 이하의 정수입니다. 이는 K209가 청량리역이고 K272가 인천역이기 때문입니다.

하행에서의 역 번호가 Kddd인 역의 다음 역은, 역 번호가 K272인 인천역을 제외하고, 정수 ddd + 1의 값이 DDD일 때 KDDD가 됩니다.

하행 열차는 아래와 같은 알고리즘으로 운행하게 됩니다.

1. 시발역에서 HH시 mm분에 출발해서, 다음역으로 이동하게 됩니다.
2. 열차가 역에 도착했다면 20초 동안 역에 머무르게 됩니다. 20초가 지난 후에는 문을 닫고 출발하게 됩니다.
3. 만약에 종착역이라면 열차는 더 이상 운행하지 않습니다. 그렇지 않으면 다음역으로 이동한 후에 2번을 수행합니다.

예를 들어 하행 열차가 역 번호가 K210인 역에서 운행을 시작해서, K233 역에서 운행을 종료한다고 해 보겠습니다.

[그림 2] K233이 종착역인 하행 열차가 K232 역에 도착한 경우

그림 2는 K210 역이 시발역이고, K233역이 종착역인 하행 열차가 K232 역에 도착한 상황과, K232 역에 도착하고 20초 후 상황을 도식화 한 그림입니다.

K232은 종착역이 아니므로, K232역에 도착하고 20초 후에는 K232 역을 출발해서 K233역 방향으로 가게 됩니다.

[그림 3] K233이 종착역인 하행 열차가 K233 역에 도착한 경우

그림 3은 K210 역이 시발역이고, K233역이 종착역인 하행 열차가 K233에 도착한 상황과, K233에 도착하고 나서 20초 후의 상황을 나타냅니다.

K233은 종착역이므로 K233역에 도착한 열차는 K233에 도착하고 20초 후에 운행을 종료하게 됩니다. 운행이 종료된 열차는 그림에 표시되지 않습니다.

한 역에서 다음 역을 이동하는 시간은 표 1에 있는 경우를 제외하고 2분입니다.

[표 1] 인접 역간 소요 시간이 3분 이상인 경우

가희는 역 번호가 K225인 모란역에서 수인 분당선 열차만 타고 역 번호가 K272인 인천역에 가려고 합니다.

인천역에 가장 빠르게 도착했을 때 시각을 구해주세요.

첫 번째 줄에는 가희가 모란역에 도착한 시각이 HH:mm:ss 형식으로 주어집니다. 항상 올바른 형식의 시각으로 주어집니다.

두 번째 줄에 수인 분당선 하행 열차의 운행 정보 갯수 N이 주어집니다.

세 번째 줄부터 N+2번째 줄까지, 열차가 운행을 시작하는 시발역의 역 번호, 운행을 마치는 종착역의 역 번호, 시발역 에서의 출발 시각이 주어집니다.

시발역에서의 출발 시각은 HH:mm 형식으로 주어집니다. 항상 올바른 형식의 시각으로 주어집니다.

예를 들어, 운행 정보가 K210 K272 11:20으로 주어지면, 이는 K210(왕십리)역을 11시 20분에 출발하여, K272(인천)역에서 운행을 종료하는 열차임을 의미합니다.

인천역에 도착하는 가장 빠른 시각을 HH:mm:ss 형식으로 출력합니다.

만약, HH, mm, ss가 10보다 작다면 앞에 0을 붙여서 출력하세요. 예를 들어, 답이 9시 1분 0초라면 9:1:0이 아닌 09:01:00으로 출력해 주세요.

금일 23:59:59 까지 수인 분당선만 타고 역 번호가 K272인 인천역에 도착할 수 없다면 -1을 출력합니다.

• 1 ≤ N ≤ 400
• 열차의 시발역과 종착역은 K210, K233, K246, K258, K272 중 하나이며, 시발역은 종착역보다 사전순으로 앞에 있습니다.
• K268 (학익)역에도 열차가 멈춥니다.
• 시발 역에서 첫차는 04:45 이후에 출발하고, 막차는 23:45 이전에 출발합니다. 즉, 하행 열차의 운행 정보에 있는 시각은 04:45 이후이고 23:45 이전입니다.
• 열차의 조착이나 지연은 없습니다.
• 하행 열차 둘 이상이 같은 역에 있는 경우는 존재하지 않습니다.
• HH:mm:ss 형식과 HH:mm 형식에서 HH는 구간 [0, 23]에 속하는 정수이고, mm과 ss는 구간 [0, 59]에 속하는 정수입니다. HH, mm, ss는 10보다 작은 경우, 앞에 0이 붙습니다.

• 시발역은 열차가 운행을 시작하는 역이고, 종착역은 열차가 운행을 종료하는 역입니다. 예를 들어 시발역이 K258이고, 종착역이 K272라면, 열차는 K258(오이도)역을 출발하여 아래와 같은 순서대로 역에 멈추게 됩니다.
  • K259(달월), K260(월곶), K261(소래포구), K262(인천논현), K263(호구포), K264(남동인더스파크), K265(원인재), K266(연수), K267(송도), K268(학익), K269(인하대), K270(숭의), K271(신포), K272(인천)