I`ll Be Round About
A common traffic intersection in Europe, and one that is becoming popular in the United States, is the "roundabout". When a driver enters a roundabout, the driver yields to cars that are already in the roundabout, then proceeds in and around to the correct exit. Roundabouts may have multiple lanes entering, circling, and exiting the traffic structure, which contains a center area that is usually circular. In the U.S. the cars travel in a counter-clockwise direction, while in the United Kingdom and areas where the norm is to drive on the left, the cars circle in a clockwise manner.
A particular country, Roundoslavia, uses roundabouts for all road intersections. Also, because roundabouts are so popular, the government has decided that the center circle could be fairly large. They plan on placing parks in the center. This presents a problem for the tourism bureau at Roundoslavia; the distance between two points on a map, something that they would like to print in the tourism guides, will be longer because of the increased distance at the intersections.
Roundoslavians drive on the right side of the road, so they proceed in a counter-clockwise direction. Thus a car entering the intersection from the right (East) and exiting at the bottom (South) would make three-quarters (¾) of a circle. If the center island is 500 meters in diameter, the car will have travelled ¾ the circumference of a circle 500 meters across. In general if we consider East to be 0 degrees, North to be 90 degrees, West to be 180 degrees, and so on, we can restate this as "the car enters from zero degrees and exits at 270 degrees." Roundabouts are placed to minimize the amount of road that is needed between them, so cars may enter at an arbitrary point, say 48 degrees, and exit at 190 degrees. Also, other cars could be entering at 190 and exiting at 48.
When calculating the distances between locations on a map, the travel bureau wishes to include these extra roundabout travel distances so that the visitors to the country have an accurate estimate of how long their driving times will be.
Given data on a set of roundabouts, the roads connecting them, and the starting and ending roundabouts, determine the minimum distance between the starting and ending roundabouts and the corresponding route. The correct route will always be unique.
Input
There will be an arbitrary number of cases to consider. The input begins with a line containing a single integer that specifies the number of cases. That line is followed by the input for the first case, then the input for the second case, and so forth.
The input for each case begins with a line containing a single integer NRB (1 ≤ NRB ≤ 25) which is the number of roundabouts. This line is followed by NRB lines, with the I-th line (1 ≤ I ≤ NRB) giving the diameter of the I-th roundabout, in meters.
The next line in the input for each case contains a single integer NRD (1 ≤ NRD ≤ 100) which is the number of roads connecting the roundabouts. This line is followed by NRD lines (that is, one for each road), each containing five (5) integers separated by one or more spaces. The first two integers identify the roundabouts that are connected by the road. The third integer gives the length of the road, in meters, but does not include any of the distance that might be travelled inside the roundabouts. The fourth integer specifies the angle (in degrees) at which the road connects to the roundabout specified by the first integer. Similarly, the fifth integer specifies the angle at which the road connects to the roundabout specified by the second integer. The angles will always be non-negative and less than 360 degrees.
The last line in the input for each case contains two integers separated by whitespace. These integers identify the starting and ending roundabouts between which the minimum distance and corresponding route are to be determined.
Roads may curve slightly; leaving a roundabout at 90 degrees does not necessarily imply entry to another at 270degrees. We are not concerned with this. Also, there are no one-way roads, and there is at most one road directly connecting any pair of roundabouts.
In determining the distance traveled within a single roundabout, the calculation should be done using real numbers, and then truncated to yield an integer.
No "U-turns" are permitted at the entrance to a roundabout. To enter and exit at the same angle, the driver must go all the way around—360 degrees.
Example: Consider the input shown in the Sample Input (below). There are two cases to consider. The first case has 9 roundabouts (with diameters 500, 450, …, 1500) and 12 roads. The first road connects roundabouts 6 and 1, and has a distance of 15000 meters. It connects to roundabout 6 at 0 degrees, and to roundabout 1 at 180 degrees. For this case, you are to find the appropriate route between roundabouts 6 and 9.
Note that there is no extra distance associated with entering or leaving the endpoints. In the first example case, initially leaving roundabout six adds no additional distance, and entering roundabout nine also adds no additional distance. As a simple example, suppose you were asked for the distance between roundabouts one and six. This would be just 15000 meters. As another example, the distance from one to one is zero meters. The route in this case is 1.
Output
For each input case, print the case number (1, 2, …), the distance between the starting and ending points, and the route using the format shown. Indent the "Distance: " and "Path: " lines three spaces, and include a blank line as the last line in the output for each case. Follow the format shown.