Problem F
River Crossing
Input: Standard Input

Output: Standard Output

A group of travelers have reached a river, which they intend to cross by building a small raft. However, they're terrified of the water as they can't swim, and they fear the raft might break apart any moment while they're using it. So, they would like to cross the river by traveling as little as possible over water. The river also contains some islands. They can use the raft to reach an island and then carry the raft over land and leave the island at some other point. The picture bellow shows a possible scenario. The shortest distance, counting only the distance over water, is shown with black straight lines (red for online contestants) on the river.

Write a program which, given the shape of the river (two sequences of connected line segments) and the islands (simple polygons), calculates the shortest distance required to travel over water in order to cross the river. The travelers must cross the river within the area of the map.

Input

The input consists of several scenarios. The first line contains the number of scenarios (at most 20). Next follows each scenario.

Each scenario starts with a line containing three integers: r1, r2 (2 <= r1, r2 <= 100) and n (0 <= n <= 11). Then follows r1 pair of integers, describing the coordinates (x,y) of one river bank. This is followed by another r2 pair of integers, describing the other river bank. The two river banks will not intersect nor touch each other.

Next follows the description of n island. Each island description starts with an integer m (3 <= m <= 20), the number of vertices in the polygon. Then follows m pairs of integers describing the coordinates (x,y) of the polygon, either in clockwise or counter clockwise direction. All islands will be simple polygons that lie between the two river banks, and they will neither overlap nor touch each other or the river banks.

All coordinates in the input will be between 0 and 10,000, inclusive. The two sequences of line segments describing the riverbanks will both start at x-coordinate 0 and end at same positive x-coordinate. All other x-coordinates in the input for that scenario, including those for the islands, will have x-coordinates between these two endpoints.

All integers in the input will be separated by at least one space or new line.

Output

For each scenario, output on a line by itself the shortest distance that must be travelled on water to cross the river. The precision should be to 3 decimal places, correctly rounded.

Sample Input

2
 
15 14 4
0 9 7 7 10 7 16 11 20 12 24 11 25 9 24 4 25 2 31 1 38 3 41 11 44 15 49 17 51 17
0 19 3 20 8 19 11 19 15 21 21 23 25 23 26 20 26 18 34 19 37 21 42 23 47 24 51 24
4
5 11 9 11 7 15 4 14
3
17 14 16 16 19 17
3
28 15 33 13 30 17
6
31 5 27 7 29 12 31 8 35 9 34 6
 
2 2 0
0 0 1000 0
0 100 1000 100
 

Sample Output

6.256
100.000

Note: The first scenario in the sample input corresponds to the map on the picture.


Problemsetter: Jimmy Mårdell