가희와 중부내륙선

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

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

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

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

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

1. 구간 A ~ B를 운행하는 열차가 있는 경우, 다른 열차가 구간 A ~ B에 접근하는 것을 허용하지 않습니다.

2. 그렇지 않은 경우

   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이 붙습니다.

• 시발역은 열차가 운행을 시작하는 역이고, 종착역은 열차가 운행을 마치는 역입니다.

• 문제의 단순화를 위해 아래의 요소들은 무시하셔도 좋습니다.

  • 앙성온천 ~ 충주 구간에 있는 금가 신호장
  • 부발역 근처에서 경강선 전철과의 경합
  • 부발 기지에 속해 있는 이음 편성의 수