마르코프 열차

네덜란드 철도 회사 NS는 요즘 사정이 좋지 않다. 기술적인 문제 때문에 예고 없이 많은 열차 운행을 취소해야 하는데, 이는 집에서 학교까지 열차로 통학하는 학생들에게 큰 불편이다.

가장 곤란한 점은 취소가 무작위로 일어난다는 것이다. 어떤 운행이 취소될지는 아무도 미리 알 수 없으며, 취소 사실은 예정된 출발 시각이 되어서야 공지된다. 집에서 학교까지 가는 경로는 보통 여러 개이므로, 승객들은 "미리 알았더라면 다른 경로로 갔을 텐데" 하고 아쉬워하기 일쑤다.

이 문제를 돕기 위해 NS 통계 부서는 어떤 운행이 다른 운행보다 더 자주 취소된다는 사실을 발견하고, 이 정보를 공개하기로 했다. 새 시간표에는 각 운행의 출발·도착 시각뿐 아니라 취소 확률도 함께 표시된다.

평소 역과 역 사이의 가장 빠른 경로를 찾아 주던 NS의 경로 안내 소프트웨어를, 이제는 제시간에 도착할 확률이 가장 높은 경로를 찾도록 개선해야 한다. 그러면 승객은 취소되기 쉬운 열차를 피하고, 조금 더 걸리더라도 더 안정적인 경로를 택할 수 있다.

새 시간표와 출발역·가장 이른 출발 시각, 도착역·희망 도착 시각이 주어질 때, 제시간에 도착할 확률이 가장 높은 경로를 구하라.

여기서 경로란 출발역에서 시작해 도착역에서 끝나는, 승객이 거쳐 가는 역들의 순서 있는 목록일 뿐이다. 승객은 이 경로를 그대로 따른다. 각 역에서 경로상 다음 역으로 가는, 탈 수 있는 첫 열차를 탄다. 그 열차가 취소되면 같은 역으로 가는 다음 열차를 기다린다.

제시간에 도착할 확률이란, 위와 같이 경로를 따르는 승객이 희망 도착 시각 또는 그 이전에 도착역에 도착할 확률이다. 이 확률을 계산할 때, 각 열차의 취소는 서로 독립이며 시간표에 적힌 확률에 따라 일어난다고 가정한다.

첫 번째 줄에는 실행 횟수를 나타내는 양의 정수 하나가 주어진다. 각 실행의 입력은 다음과 같다.

• 시간표에 있는 열차의 수 $n$ ($n \le 100$)이 한 줄에 주어진다.
• 이어서 $n$개의 줄에 각 열차가 주어진다. 각 줄은 출발역 $x$, 출발 시각 $t_x$, 도착역 $y$ ($x \ne y$), 도착 시각 $t_y$ ($t_x < t_y$), 취소 확률 $p$로 이루어진다. 역은 A부터 L까지의 대문자로 표기한다. 시각은 hh:mm 형식이며 $00 \le hh < 24$, $00 \le mm < 60$이다. 확률 $p$는 $0.0 \le p < 1.0$인 십진 실수이다. 각 항목은 공백으로 구분된다.
• 마지막 줄에는 출발역 $a$, 가장 이른 출발 시각 $t_a$, 도착역 $b$ ($a \ne b$), 희망 도착 시각 $t_b$ ($t_a < t_b$)가 위와 같은 형식으로 주어진다.

각 실행마다 두 줄을 출력한다. 첫 번째 줄에는 최적 경로를 역 식별자들의 공백으로 구분된 목록으로 출력한다. 두 번째 줄에는 그 경로를 따를 때 제시간에 도착할 확률을, 소수점 앞에 정확히 한 자리, 소수점 뒤에 정확히 네 자리로 출력한다. 반올림은 일반적인 규칙을 따른다. 다음 자리가 $5$ 이상이면 올림, 그렇지 않으면 버림한다.

• 중간 역에서 열차를 갈아탈 때, 가장 이른 출발 가능 시각은 도착 시각의 $1$분 후이다.
• 모든 시각은 같은 날에 속하며, 어떤 여정도 자정을 넘기지 않는다.
• 같은 역에서 같은 도착역으로 같은 시각에 출발하는 열차는 둘 이상 존재하지 않는다.
• 입력은 최대 확률을 갖는 경로가 유일하도록 주어진다.
• 승객은 항상 선택한 경로를 따르며, 다음 역으로 가는 첫 열차를 탄다. 그 열차가 취소되면 같은 역으로 가는 다음 열차를 기다린다. 더 빠른 열차나 다른 경로로 바꿔 타는 등의 영리한 행동은 하지 않는다.