열차 지연

열차를 갈아타며 목적지까지 이동하려고 한다. 이동에 걸리는 시간을 최대한 줄이고 싶지만, 열차는 지연될 수 있다.

각 열차에 대해 정시 출발 시각, 지연되지 않았을 때의 소요 시간, 지연될 확률, 그리고 지연될 때의 최대 지연 시간을 알고 있다. 각 열차가 지연되는지 여부는 서로 독립이며, 어떤 열차가 지연되는지는 미리 알 수 없고 실제로 지연이 발생할 때 비로소 알게 된다.

열차는 항상 정시에 출발하며, 도착 시각만 늦어질 수 있다. 환승에 걸리는 시간은 0이므로, 어떤 열차에서 내린 시각과 같은 시각에 출발하는 열차에 곧바로 탈 수 있다. 이동 도중 지연이 발생하면 그에 맞추어 남은 계획을 바꿀 수 있다. 첫 열차를 타는 시각은 자유롭게 정할 수 있으므로 첫 열차를 기다릴 필요는 없다.

주어진 시간표에 대해, 출발 도시에서 도착 도시까지 이동하는 데 걸리는 시간의 기댓값의 최솟값을 구하여라.

첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스의 개수는 100개를 넘지 않는다.

각 테스트 케이스의 첫째 줄에는 출발 도시의 이름과 도착 도시의 이름이 주어지며, 두 이름은 항상 서로 다르다. 다음 줄에는 열차의 수 $n$ ($1 \le n \le 1000$)이 주어진다. 이어지는 $n$개의 줄에는 각각 한 대의 열차 정보가 다음 여섯 개의 값으로 주어진다.

• 출발 도시와 도착 도시 (두 이름은 항상 서로 다르다)
• 출발 분 $m$ ($0 \le m \le 59$): 열차는 한 시간에 한 편씩 있으며 항상 $m$분에 출발한다
• 지연되지 않았을 때의 소요 시간 $t$ ($1 \le t \le 300$), 단위는 분이다
• 지연될 확률 $p$ ($0 \le p \le 100$), 단위는 퍼센트이다
• 최대 지연 시간 $d$ ($1 \le d \le 120$), 단위는 분이다

열차가 지연될 때, 지연 시간은 $[1, d]$ 구간에서 균일하게 뽑힌 정수 분이다. 모든 도시의 이름은 알파벳 대문자와 소문자로만 이루어지며 길이는 20을 넘지 않는다.

각 테스트 케이스에 대해, 이동 시간의 기댓값의 최솟값을 기약분수 p/q 형태로 출력한다. 이때 $q \ge 1$이고 $\gcd(p, q) = 1$이며, 값이 정수 $a$이면 a/1로 출력한다. 도착 도시에 갈 수 없는 경우에는 대신 IMPOSSIBLE을 출력한다.

입력의 모든 값이 유리수이므로 이동 시간의 기댓값은 항상 유리수이며, 위와 같은 분수로 정확히 나타낼 수 있다.