Train delays

Last year, some of the judges tried to travel to NWERC’10 by train. This turned into a big disaster: on the way there, a fire in a control room caused huge delays, while on the return trip, trains in Bremen were delayed due to a terrorist threat in Hamburg. Of course, these huge delays caused other delays in the train schedule, so the big question was which trains to take: would it be better to take this slow regional train now, or wait for that intercity train, which has a big chance of being delayed?

This year, the judges have planned ahead and carefully analyzed the train schedule. They even kept track of how often trains were delayed and by how much. Now that they have all this information, they want to travel as quickly possible, minimizing the expected duration of the journey. Can you help them?

For each train connection, the judges know exactly what its scheduled departure time and duration are, as well as the probability that its arrival at the destination will be delayed. You may assume that the probabilities of delays are independent and that the judges can adapt their itinerary as they go, depending on any delays which they might already have incurred. Trains always depart on time, but may arrive late and the judges do not know whether a train’s arrival will be delayed until they have boarded it. It takes judges no time to switch trains, so they can take a connecting train that departs at the same time as they arrive at a place.

The judges can choose the time of their initial departure as they wish and they want to minimize the expected duration¹ of their total trip.

Input

On the first line a positive integer: the number of test cases, at most 100. After that per test case:

• one line with the judges’ place of origin and destination, these are different.
• one line with an integer n (1 ≤ n ≤ 1 000): the number of train connections.
• n lines, each describing a train connection:
  • the origin and destination of this connection, these are different.
  • an integer m (0 ≤ m ≤ 59), the departure time in minutes after each full hour.
  • an integer t (1 ≤ t ≤ 300), the standard journey time (assuming no delays).
  • an integer p (0 ≤ p ≤ 100), the probability of delays as a percentage.
  • an integer d (1 ≤ d ≤ 120), the maximum delay in minutes.

All place names are given as strings of upper and lower case alphabetical characters, of length at most 20. If a train is delayed, then the length of the delay will be a whole number of minutes, and will be uniformly distributed in the range [1,d].

Output

Per test case:

• one line with a floating point number: the minimum expected duration of the total trip in minutes.

This number should be accurate up to 10^-6 relative or absolute precision. Output IMPOSSIBLE instead if the destination is not reachable.

Sample in- and output

3
Hamburg Bremen
3
Hamburg Bremen 15 68 10 5
Hamburg Bremen 46 55 50 60
Bremen Frankfurt 14 226 10 120
Amsterdam Rotterdam
1
Amsterdam Utrecht 10 22 5 10
BremenVegesack Utrecht
9
BremenVegesack BremenHbf 15 10 0 1
BremenVegesack BremenHbf 45 10 0 1
BremenVegesack Leer 23 140 10 15
BremenHbf Osnabruck 44 51 60 70
Osnabruck Amersfoort 55 147 38 40
Amersfoort Utrecht 24 15 30 15
Amersfoort Utrecht 54 15 10 35
Leer Groningen 45 140 5 10
Groningen Amersfoort 46 96 10 20

68.3
IMPOSSIBLE
305.0532857 

Note in the first example that it is better to take the slower train from Hamburg to Bremen, since the fast train would give an expected travel time of 70.25 minutes.

¹Given a travel plan of which trains to take (depending on previous connections and delays), the expected trip duration E is defined to be the sum of the trip duration T_i for each itinerary i possibly taken multiplied by the chance p_i of that itinerary occurring: E = ∑ _ip_i T_i.

Copyright notice

This problem text is copyright by the NWERC 2011 jury. It is licensed under the Creative Commons Attribution-Share Alike license version 3.0; The complete license text can be found at: http://creativecommons.org/licenses/by-sa/3.0/legalcode