Markov Trains

Business is not going well for the Dutch railway operator NS. Because of technical failures they are forced to cancel many train services without any warning, which is extremely frustrating for students who commute from home to school by train.

The worst part is how random the cancellations are. Nobody knows in advance whether a service will run; a cancellation is only announced at the scheduled departure time. Since there is usually more than one route from home to school, travelers are often left thinking "if only I had known, I would have taken the other route."

To help passengers, the statistics department of NS noticed that some services are cancelled more often than others and decided to publish this information. The new timetable lists, for every service, not only its departure and arrival time but also its probability of cancellation.

The NS route-planning software, which normally finds the fastest route between stations, must be updated to instead find the route that gives the best chance of arriving on time. This lets passengers avoid trains that are likely to be cancelled in favor of a slightly longer but more reliable trip.

Given the new timetable, a departure station and time, a destination station and a desired arrival time, find the route that maximizes the probability of reaching the destination on time.

A route is simply an ordered list of the stations the passenger visits, starting at the departure station and ending at the destination. The passenger follows this route strictly: at each station he takes the first available train to the next station on the route. If that train is cancelled he waits for the next train to the same station.

The probability of arriving on time is the probability that a passenger who follows the route as described above reaches the destination at or before the desired arrival time. When computing this probability, cancellations are assumed to be independent of one another and to occur with the probabilities listed in the timetable.

The first line contains a single positive integer, the number of runs. Each run is given as follows.

• A line with a single positive integer $n$, the number of trains in the timetable ($n \le 100$).
• $n$ lines describing the timetable. Each line describes one train by its departure station $x$, departure time $t_x$, destination station $y$ ($x \ne y$), arrival time $t_y$ ($t_x < t_y$) and cancellation probability $p$. Stations are capital letters from A to L. Times use the format hh:mm with $00 \le hh < 24$ and $00 \le mm < 60$. The probability $p$ is a decimal real number with $0.0 \le p < 1.0$. Fields are separated by spaces.
• A line with the departure station $a$, earliest departure time $t_a$, destination station $b$ ($a \ne b$) and desired arrival time $t_b$ ($t_a < t_b$), in the same formats as above.

For each run print two lines. The first line is the best route, given as a list of station identifiers separated by spaces. The second line is the probability of arriving on time when following that route, formatted as a decimal number with exactly one digit before the decimal point and exactly four digits after it. Use ordinary rounding: round up when the next digit would be $\ge 5$, and round down otherwise.

• When changing trains at an intermediate station, the earliest possible departure time is one minute after the arrival time.
• All times fall on the same day; no journey crosses midnight.
• No two trains ever depart from the same station at the same time toward the same destination station.
• The input is such that the route with maximum probability is unique.
• The passenger always follows the chosen route, taking the first available train to the next station; if it is cancelled he waits for the following train to that station. He never tries to be clever by switching to faster trains or different routes.