A castle can be regarded as a convex polygon with vertices on the plane, whose vertices are in counterclockwise order.

The king sent soldiers to patrol outside the castle. The patrol route of the -th soldier is a line segment from to that lies strictly outside the castle. Each soldier carries a lantern that can be regarded as a point light source, and once the light touches the boundary of the castle, it will no longer propagate any further (and no reflection or similar phenomenon occurs).

To evaluate the patrol strength, the king wants to know: during the patrol, what is the total length of the castle boundary that each soldier can see with the help of the lantern?

输入描述:

The first line contains a positive integer  (), denoting the number of test cases.

For each test case, the first line contains two positive integers  (, ), denoting the number of vertices of the convex polygon and the number of soldiers.

The next  lines give the vertices of the castle's convex polygon in counterclockwise order. The -th line contains two integers  (), denoting the coordinates of vertex . It is guaranteed that no three of these  points are collinear.

The next  lines each contain four integers  (), denoting the patrol route of the -th soldier. It is guaranteed that the patrol route lies strictly outside the castle and does not intersect the castle boundary. Be aware that  and  may be the same.

For all test cases, it is guaranteed that the sum of  and the sum of  do not exceed .

输出描述:

For each soldier in each test case, output one real number per line, representing the total length of the castle boundary that the soldier can see with the help of the lantern. Your output will be accepted if the absolute or relative error between your output and the answer does not exceed .

2
4 4
0 0
10 0
10 10
0 10
2 -5 8 -5
15 -5 20 -5
-5 -5 15 -5
-5 5 5 16
3 3
0 0
12 0
0 5
-2 -2 14 -2
6 6 14 6
-5 6 15 6

10.0000000000
20.0000000000
30.0000000000
20.0000000000
17.0000000000
13.0000000000
18.0000000000

备注:

The figure shows the castle boundary as seen by the first soldier, which is marked as red, in the first test case.