D30:color tunnels (color tunnels, translation)

The original title is ：OpenJudge - 687:Color Tunnels

translate ：

describe ： A toy company has a complex system to paint products . In order to get the desired color , The product must be painted in several colors in the specified order . Every product is colored through a color tunnel . For each color , At least one channel is drawn with this color （ There may be more ）. Tunnels are distributed in the spraying area , Products must be transported from one tunnel to another , To paint the given color . When the painting process starts , The product is at a certain point in the production plant , Finally, it must be delivered to the product warehouse ;
        Officially , The uncolored finished product is at the source , It must be painted with different colors in the given order before it can be transported to another destination . There are several tunnels , Each tunnel is considered to operate simultaneously , Tunnels have specific colors , But the color is not necessarily different . set up < c1,c2,……,cn > Is the product to be painted n A sequence of colors . The product needs to pass < t1,t2,……> bring ti The color of is ci. Be careful , It is possible to cross the tunnel without being painted , therefore , actually , Aforementioned < t1,t2,...,tn > It may be a subsequence of the tunnel through which the product passes . The direction in which the product passes through the tunnel is not important . The goal is to find the shortest path from the source point to the destination under the limitation of color . This road may cross itself , Even through the tunnel . Twice is also allowed ( Or more times ) Through the tunnel .
Be careful ！ Two tunnels can cross or overlap , But they are different ;
Input ： Contains several test cases . The first line of input is a no greater than 20 The positive integer t, Represents the number of test cases . After the first line is t Data of test cases . The first line of each test case contains four real numbers xs,ys,xt,yt, They are source and destination x and y coordinate . The second line contains the color sequence ： The first number is the length of the sequence , The scope is [1,30], The remaining line is the sequence itself . Each color in the sequence is in the range [1,100] The integer of . The third line contains the scope [1,60] It's an integer of , Indicates the number of tunnels , Heel n That's ok , Each line contains five numbers . The first two numbers are at one end of the tunnel x and y coordinate . The third and fourth numbers are on the other side x and y coordinate . Coordinates are real numbers . The fifth number belongs to [1,100];
Output ： Yes t That's ok , Each row contains the minimum length of the path from the source point to the destination , Constrained by the problem . The length will be compared with the best length within the accuracy range of three digits after the decimal point .