Train Delays

You are planning a train journey with transfers and want to spend as little time traveling as possible, but trains can be delayed.

For every train you know its scheduled departure time, its travel time when it runs on time, the probability that it is delayed, and how long such a delay can be. Whether a given train is delayed is independent of every other train, and you cannot know in advance whether a train will be delayed; you only find out when the delay actually happens.

Trains always leave exactly on schedule; only the arrival can be late. Changing trains takes no time, so you may board a train that departs at the very same minute another train drops you off. If a delay occurs along the way, you may revise the rest of your plan to account for it. You may choose the moment you board your very first train freely, so you never have to wait for it.

Given the schedule, compute the minimum possible expected total travel time from the start city to the destination city.

The first line contains the number of test cases, which is at most 100.

Each test case begins with a line containing the name of the start city and the name of the destination city; these two names are always different. The next line contains the number of trains $n$ ($1 \le n \le 1000$). Each of the following $n$ lines describes one train with six fields:

• the departure city and the arrival city (always two different names)
• the departure minute $m$ ($0 \le m \le 59$): the train runs once every hour and always leaves at minute $m$
• the travel time $t$ ($1 \le t \le 300$), in minutes, when the train is not delayed
• the delay probability $p$ ($0 \le p \le 100$), as a percentage
• the maximum delay $d$ ($1 \le d \le 120$), in minutes

When a train is delayed, the delay is an integer number of minutes drawn uniformly from $[1, d]$. Every city name consists of uppercase and lowercase letters only and has length at most 20.

For each test case, print the minimum expected total travel time as an irreducible fraction p/q, where $q \ge 1$ and $\gcd(p, q) = 1$; if the value is an integer $a$, print it as a/1. If the destination city cannot be reached, print IMPOSSIBLE instead.

Every input quantity is rational, so the expected travel time is always a rational number and can be given exactly as such a fraction.