Color Tunnels

Time limit1sMemory limit128 MB

Summary

Given a color sequence and colored line-segment tunnels, find the shortest path from source to destination that traverses tunnels in the required color order.

Level: Hard8 of 10
Topics: Geometry, Shortest path, Dynamic programming
Solved: No attempts yet

Problem

A toy factory paints its products by moving them through colored tunnels. To reach a desired final color, a product must be painted by an ordered sequence of colors.

Each tunnel is a straight line segment of a fixed color, placed somewhere in the plane. A single color may be produced by several tunnels, and different tunnels may share the same color. To be painted with a color, the product must travel through a tunnel of that color from one endpoint to the other (a full traversal); the direction of travel does not matter.

Formally, an unpainted product starts at a given source point and must be delivered to a given destination point after being painted, in order, with the colors $c_1, c_2, \ldots, c_n$ . The product must therefore traverse tunnels $t_1, t_2, \ldots, t_n$ (in this order) such that tunnel $t_i$ has color $c_i$ . It may also pass through or cross other tunnels along the way; only the chosen subsequence $t_1, \ldots, t_n$ has to match the required colors. Between traversals the product moves along straight line segments through the obstacle-free plane. The path may cross itself or merely intersect a tunnel without traversing it (which does not count as painting), and the same tunnel may be traversed more than once.

Compute the length of the shortest such path from the source to the destination.

Input

The first line contains an integer $t$ ( $1 \le t \le 20$ ), the number of test cases. Each test case is given as follows.

One line with four real numbers $x_s\ y_s\ x_t\ y_t$ : the coordinates of the source $(x_s, y_s)$ and of the destination $(x_t, y_t)$ .
One line describing the color sequence: an integer $m$ ( $1 \le m \le 30$ ) giving its length, followed by $m$ integers $c_1, \ldots, c_m$ (each in $[1, 100]$ ), the required colors in order.
One line with an integer $n$ ( $1 \le n \le 60$ ), the number of tunnels.
$n$ lines, each with five numbers $x_1\ y_1\ x_2\ y_2\ c$ : the endpoints $(x_1, y_1)$ and $(x_2, y_2)$ (real numbers) and the color $c$ (an integer in $[1, 100]$ ) of one tunnel.

Every color that appears in a sequence is produced by at least one tunnel, so a valid path always exists.

Output

For each test case, print a single line containing the minimum total travel length from the source to the destination that traverses tunnels matching the required color order, rounded to exactly three digits after the decimal point.

Examples3

Example 1

Input

1
0 1.5 100 67
4 1 4 3 1
9
10 10 20 20 1
10 15 20.5 35.333 3
30 15 14.55 12.5 1
40 30 44 33 1
29 84 33 58 4
9 39 41 115 2
75 47 37 69 4
46 26 58 25 3
73 48 27 59 3

Expected output

240.610

Example 2
Input
```
1
0 0 10 0
1 5
1
3 0 7 0 5
```
Expected output
```
10.000
```
Example 3
Input
```
1
0 0 0 0
1 2
1
3 4 3 -4 2
```
Expected output
```
18.000
```