가희와 수인 분당선 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(인천)