가희와 중부내륙선

시간 제한1초메모리 제한512 MB

요약

단선 구간에서 관제 허가를 기다리며 운행하는 열차들을 시뮬레이션하고, 편성 번호 순서로 종착역 도착 시각을 출력합니다.

난이도: 보통10점 중 6점
유형: 시뮬레이션, 정렬, 구현
정답자: 아직 제출이 없습니다

문제

중부 내륙선은 2021년 12월 31일에 개통된 단선 철도입니다. 하행 열차는 부발역을 출발하여 가남, 감곡장호원, 앙성온천, 충주 순으로 멈추고, 상행 열차는 충주를 출발하여 앙성온천, 감곡장호원, 가남, 부발역 순으로 멈춥니다. 각 구간의 소요 시간은 [표 1]과 같습니다.


구간	소요 시간
부발 ~ 가남	7
가남 ~ 감곡장호원	7
감곡장호원 ~ 앙성온천	8
앙성온천 ~ 충주	10

[표 1] 각 구간의 소요 시간

중부내륙선은 단선이어서, 구간에는 한 열차만 운행할 수 있습니다. 하지만, 역에는 상행 열차 여러 대와 하행 열차 여러 대가 동시에 정차할 수 있습니다. 하행 열차와 상행 열차는 아래 알고리즘으로 운행됩니다.


순번	하행	상행
1	부발역에서 HH시 mm분에 문을 닫는다.	충주역에서 HH시 mm분에 문을 닫는다.
2	구간 부발 ~ 가남을 운행한다.	구간 앙성온천 ~ 충주를 운행한다.
3	1분간 가남역에 머무르고 문을 닫는다.	1분간 앙성온천역에 머무르고 문을 닫는다.
4	구간 가남 ~ 감곡장호원을 운행한다.	구간 감곡장호원 ~ 앙성온천을 운행한다.
5	1분간 감곡장호원역에 머무르고 문을 닫는다.	1분간 감곡장호원역에 머무르고 문을 닫는다.
6	구간 감곡장호원 ~ 앙성온천을 운행한다.	구간 가남 ~ 감곡장호원을 운행한다.
7	1분간 앙성온천역에 머무르고 문을 닫는다.	1분간 가남역에 머무르고 문을 닫는다.
8	구간 앙성온천 ~ 충주를 운행한다.	구간 부발 ~ 가남을 운행한다.
9	충주역에 도착하면 운행을 종료한다.	부발역에 도착하면 운행을 종료한다.

[표 2] 하행, 상행 열차의 운행 알고리즘

표 2는 하행 열차와 상행 열차가 시발역에서 종착역까지 가기 위해서 수행하는 일들을 나타냅니다. 이 중 순번 2, 4, 6, 8은 구간을 운행하는 것이므로 관제의 허가를 받아야 합니다. 허가를 받지 못하면 받을 때까지 대기했다가 수행합니다. 하행에서의 A역 다음 역이 B역이라고 했을 때, 관제는 구간 A ~ B에 대해서

구간 A ~ B를 운행하는 열차가 있는 경우, 다른 열차가 구간 A ~ B에 접근하는 것을 허용하지 않습니다.
그렇지 않은 경우
1. A역에서 구간 A ~ B를 운행하려고 하는 하행 열차 h만 있다면, h가 구간 A ~ B를 운행하는 것을 허용합니다.
2. B역에서 구간 A ~ B를 운행하려고 하는 상행 열차 s만 있다면, s가 구간 A ~ B를 운행하는 것을 허용합니다.
3. 그렇지 않은 경우
  1. 시발역에서 먼저 운행을 시작한 열차가 구간A ~ B를 운행하는 것을 허용합니다.
  2. 2 - 3 - 1로도 결정할 수 없다면, 편성 번호가 더 낮은 열차가 구간 A ~ B를 운행하는 것을 허용합니다.

충주로 향하는 하행 열차 C편성, 부발로 향하는 상행 열차 H편성이 있을 때, 각 편성이 종착역에 도착하는 시각을 구해 주세요.

입력

첫 번째 줄에 C와 H가 공백을 구분으로 해서 주어집니다.

다음 C개의 줄에는 충주로 향하는 하행 열차의 번호와, 해당 열차가 시발역에서 운행을 시작한 시각이 HH:mm형식으로 주어집니다.

다음 H개의 줄에는 부발로 향하는 상행 열차의 번호와, 해당 열차가 시발역에서 운행을 시작한 시각이 HH:mm형식으로 주어집니다.

출력

각 열차가 종착 (상행선의 경우 부발, 하행선의 경우 충주)역에 도착하는 시각을 열차 번호 오름차순으로 출력해 주세요. 시각은 HH:mm형식으로 출력해 주세요.

자정이 넘어 도착하는 경우, 다음날 HH:mm 에 도착했다고 출력해 주세요.

제한

H와 C는 1 이상 20 이하의 정수입니다.
주어지는 열차 번호는 다음 조건을 따릅니다.
- 3자리로 주어집니다.
- 상행선의 열차 번호는 끝자리가 짝수로, 하행선의 열차 번호는 끝자리가 홀수로 주어집니다.
- 같은 목적지로 향하는 열차에 대해, 먼저 출발한 열차의 열차 번호는 나중에 출발한 열차의 번호보다 작습니다.
시발역에서 방향이 같은 둘 이상의 열차가 동시에 출발하지 않습니다.
시각은 HH:mm형식입니다. 이때, HH는 0 이상 23 이하의 정수로, mm은 0 이상 59 이하의 정수로 주어집니다. HH와 mm은 10보다 작으면 앞에 0이 붙습니다.

힌트

시발역은 열차가 운행을 시작하는 역이고, 종착역은 열차가 운행을 마치는 역입니다.
문제의 단순화를 위해 아래의 요소들은 무시하셔도 좋습니다.
- 앙성온천 ~ 충주 구간에 있는 금가 신호장
- 부발역 근처에서 경강선 전철과의 경합
- 부발 기지에 속해 있는 이음 편성의 수

예제4

예제 1
입력
```
1 1
731 07:10
732 07:20
```
예상 출력
```
07:45
07:58
```

예제 2

입력

예상 출력

07:45
00:25
07:55

예제 3
입력
```
1 1
731 07:32
732 07:20
```
예상 출력
```
08:14
07:55
```
예제 4
입력
```
1 1
731 07:10
732 23:50
```
예상 출력
```
07:45
00:25
```