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 duration1 of their total trip.

-----Input-----
- one line with the judges’ place of origin and destination, these are different.
- one line with an integer $n$ ($1 \leq n \leq 1000$): 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\leq m\leq 59$), the departure time in minutes after each full hour.
- an integer $t$ ($1\leq t\leq 300$), the standard journey time (assuming no delays).
- an integer $p$ ($0\leq p\leq 100$), the probability of delays as a percentage.
- an integer $d$ ($1\leq d\leq 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-----
Output 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.

-----Examples-----
Sample Input 1:
Hamburg Bremen
3
Hamburg Bremen 15 68 10 5
Hamburg Bremen 46 55 50 60
Bremen Frankfurt 14 226 10 120
Sample Output 1:
68.3

Sample Input 2:
Amsterdam Rotterdam
1
Amsterdam Utrecht 10 22 5 10
Sample Output 2:
IMPOSSIBLE

见题面

见题面