题目描述

We are using a special radar to scan an area. The radar accepts a list of distances, e.g. 2, 4, 1, and a list of angles, e.g. $100^\circ$, $270^\circ$, $180^\circ$, $10^\circ$, $300^\circ$, and scans the points across all the given distances and angles. How close to some other points of interest will we be able to scan?

输入格式

The first line of the input gives three space-separated integers: $R$, $F$, $N$, representing the number of radii, the number of angles, and the number of points of interest, respectively. Then $R$ lines follow, $i$-th of which contains an integer $r_i$, representing the distance from the radar that will be scanned. Then, $F$ lines follow, each containing two space-separated integers $(f_x)_i$, $(f_y)_i$, that represent Cartesian coordinates of a point, defining the $i$-th angle. Then, $N$ lines follow, each containing two space-separated integers $x_i$, $y_i$, that represent the Cartesian coordinates of the $i$-th point.

The angle, defined by the point $(f_x)_i$, $(f_y)_i$ is the angle from the $x$-axis to the ray from the origin through $(f_x)_i$, $(f_y)_i$.

输出格式

Output $N$ lines, $i$-th of which should contain the distance from the point $(x_i, y_i)$ to the closest scanned point. The result will be considered correct if it is within the $10^{-6}$ of absolute or relative precision.

3 7 5
2
4
7
8 4
2 8
-1 5
-7 2
-4 -4
1 -8
6 -3
3 -1
8 1
2 6
-5 2
-1 -1

0.977772290466
2.750120773895
0.846777708005
1.464071052924
0.585786437627

提示

Comment

Illustration of sample case:

:::align{center} :::

Input limits

• $1 \leq R, F, N \leq 10^5$
• $|x_i|, |y_i|, |(f_x)_i|, |(f_y)_i|, r_i < 10^6$
• $(f_x)_i^2 + (f_y)_i^2, r_i > 0$
• All $r_i$ are pairwise distinct.
• Rays, defined by $(f_x)_i, (f_y)_i$, are pairwise distinct.