The Moon of Valencia

Everybody knows the Moon of Valencia is magical, and everybody talks about the mystery that happens under it at night. People remember what time they entered the first bar, what time they reached the hotel and how happy they were when they arrived, but nobody remembers the bars and pubs in between.

The Valencia hotels have hired you to write the program that helps their customers remember. A customer gives the departure time and place, the arrival time and place, and the degree of satisfaction on arrival. The program decides whether a night that matches the story is possible at all.

The program works on a map with the location of every bar and pub. Entering a place adds its own degree of satisfaction. Walking from one place to another makes people angry, so it lowers the degree of satisfaction instead: one point for every minute spent walking, and seconds that do not fill a whole minute count as their fraction of a minute, so 30 seconds cost 0.5 points. Everybody walks at 4 km/h. A customer may stay in a bar or pub as long as they like, but only a stay of at least 15 minutes earns its satisfaction.

A customer does not have to enter every place on the way. Any subset of the places along the route may be entered, and entering the departure place is optional too. The satisfaction is counted up to the door of the target place, so the grade of the target place itself is never added. A route may not pass through the same place twice.

The whole night has to fit between the departure time and the arrival time. The walking time plus 15 minutes for every place entered may not exceed that interval. Time left over is not a problem, because the customer can sit longer in the places they entered.

The input consists of several test cases. Each case begins with the description of a map, followed by the list of arrivals the program has to check.

The description of a map begins with the word MAP in capital letters followed by two integers $P$ and $M$, where $P$ is the number of places and $M$ is the number of paths connecting two places ($1 \le P \le 64$). The next $P$ lines describe one place each, with two coordinates (real numbers in kilometres), its grade of satisfaction (a real number), its ID and its name. The next $M$ lines describe one path each, with the IDs of the two places it connects. Each pair of places is connected by at most one path, and no two paths cross.

After the map comes a line with the word ARRIVALS in capital letters, and then one line per arrival with the departure time, the departure place, the arrival time, the arrival place and the degree of satisfaction on arrival, a real number. Times are written as hh:mm on a 24-hour clock, and an arrival time earlier than the departure time means the customer got in after midnight.

For each case print a line with the word MAP in capital letters followed by the number of the case. The first case is MAP 1, the second is MAP 2, and so on.

Then print one line per arrival, in the order the arrivals are given. Print Possible! when at least one route matches the customer's story, and Impossible! when none does.

A route matches the story when it follows paths of the map, never passes through the same place twice, fits between the departure time and the arrival time, and reaches a degree of satisfaction whose absolute difference from the required one is less than 0.1.

Write the search so that it runs as fast as possible. The example case is a good measure: whatever handles it comfortably handles the rest.

Figure 1: the first map of the example input.