Rikka with Rain

Problem Description

There will always be sudden heavy rain in summer. When the heavy rain begins, there are $m$ students on the campus. We can consider each student as a circle with radius $r$ and center $(a_i,b_i)$. There is only one building in the school. This building can be considered as a simple polygon with $n$ vertices $(x_i,y_i)$. To get out of the rain, the students need to run into the building as quickly as possible. As a member of the students, Rikka wants to calculate the minimum possible running distance for each student. The following are some supplements to this task:

1. You may assume that students will not interact with each other and the circles may overlap.
2. A student is inside the building if and only if the circle is completely inside the simple polygon.
3. Students can run in any direction, and the running distance is the Euclidean distance between the initial position and the target position of the center.

Input

The first line contains a single integer $t(1 \leq t \leq 10)$, the numebr of the testcases. For each testcase, the first line contains three integers $n,m,R(3 \leq n,m \leq 200, 1 \leq R \leq 10^6)$. Then $n$ lines follows, each line contains two integers $(x_i,y_i)(|x_i|,|y_i| \leq 10^6)$, which describe the simple polygon in counter-clockwise. Then $m$ lines follows, each line contains two integers $(a_i,b_i)(|a_i|,|b_i| \leq 10^6)$, which describe the initial position of the students. The input guarantees that it is possible for each student to run into the building.

Output

For each query, let $w$ be the minimum running distance of the student. To avoid precision problem, you need to round $w$ to the nearest integer and print the result. The input guarantees that the first decimal digit of the answer will not be $4$ or $5$ and the answer will not change if we add or subtract $R$ by $0.1$.

Sample Input

1

4 4 2

0 0

4 0

4 4

0 4

1 0

2 0

10 10

-1 -2

Sample Output

2

2

11

5

Source

2018 Multi-University Training Contest 9