Peek

Problem Description

There is a large cave with words written on its inner wall, and Bob wants to see these words. Unfortunately, the interior of the cave has a large number of traps, thus making it difficult to enter; fortunately, the cave has been opened up with many windows at the corners, through which one can peek at the texts. In the process of looking in through a particular window, the edge of the polygon might be parallel to the line of sight, and then it would be difficult to see the writing on the inner wall. At this moment, you can make the inner wall no longer parallel to the line of sight, by making small movements by the window.

Formally, The large cave can be viewed as a polygon $P$ which doesn't intersect with itself, with many of its vertices $\{P_i\}$ serving as windows. When observing from the outer area of a polygon into a vertice $A$ serving as a window, the observer's line of sight will be restricted by two edges adjacent to $A$, which is shown in the following graph. Segments observable from $A$ will contribute to the total length of the answer. In addition, the observer can make a tiny movement $\varepsilon$ parallel to the window, thus making some of the edge observable.

It is guaranteed that the point which is chosen as a window will form an angle $\le 180\degree$ with its two adjacent edges. Now, Bob wants to know what is the total inner wall length that can be seen by peering through all the windows. Please note that $\varepsilon$ can be seen as a very small number, and it multiplied with any constant $k$ won't make contribute to the final answer.

Input

The first line consists of an integer $T(1\le T\le 10)$, denoting the number of test cases. In each test case, the first line gives two integers $n(1\le n\le 100$), $m(1\le m\le n$), indicating the number of vertices of the polygon and the number of windows. The next section consists of $n$ lines, each line giving two integers $x(-10^9\le x\le 10^9)$, $y(-10^9\le y\le 10^9)$, indicating the coordinates of the corresponding points. The next $m$ line gives $m$ integers, indicating the subscripts of windows. It is guaranteed that the two adjacent points will have adjacent subscripts. For example, if point $A$ and point $B$ are adjacent in the polygon, and $A$ is $P_2$, then $B$ will be $P_1$ or $P_3$.

Output

Outputs one float number with $3$ decimal places, representing the total length that can be seen.

Sample Input

2
5 1
0 0
2 0
1 1
2 2
0 2
2
12 2
3 0
5 0
5 3
3 3
3 5
6 5
6 6
0 6
0 2
3 2
3 1
0 1
1
12

Sample Output

5.414
14.162

Hint

The examples are illustrated in the following graphs. Example 1: The final answer is $2+2+\sqrt{2}=4+\sqrt{2}$.

Example 2: The final answer is $2+3+2+1+3+\sqrt{10}=11+\sqrt{10}$.

Source

2023“钉耙编程”中国大学生算法设计超级联赛（9）