Typhoon

Problem Description

A terrible typhoon is about to make landfall, and you decide to leave your home and seek refuge. We can regard the problem as occurring on a two-dimensional plane. You have $n$ alternative shelters, and you need to choose one to go to. Specifically, the $i$-th shelter is located at point $(X_i, Y_i)$ . Now the meteorological station gives the predicted typhoon track, which consists of $m$ forecast points $(x_1,y_1),(x_2,y_2),\dots,(x_m,y_m)$ , where $(x_1,y_1)$ is the starting point and $(x_m,y_m)$ is the ending point. According to the forecast, the center of the typhoon will moves along the segments between two adjacent points in turn. In order to simplify the model, it is assumed that the influence range of typhoon is a circle with radius $r$ and the radius will never change during the move. If a point will be within or just on the boundary of the typhoon's influence range at a certain time, then we consider this point to be unsafe. The radius of a typhoon is unpredictable. So you want to know, for each shelter, what is the minimum typhoon radius that still makes it unsafe.

Input

Please note that unlike other problems, there is only one test case input for this problem. The first line contains two integers $m,n\ (2\le m,n\le 10^4)$, indicating the number of forecast points of the typhoon track and the number of shelters. Then the following $m$ lines, each line contains two integers $x_i,y_i\ (|x_i|,|y_i|\le 10^9)$, indicating the coordinates of the $i$-th forecast points of the typhoon track. Then the following $n$ lines, each line contains two integers $X_i,Y_i\ (|X_i|,|Y_i|\le 10^9)$, indicating the coordinates of the $i$-th shelter.

Output

Output $n$ lines, the $i$-th line contains a single real number $r_i$ , represents the answer for the $i$-th shelter. All the real number you output should be rounded into 4 decimals.

Sample Input

7 3
10 0
6 1
4 1
4 2
3 2
3 3
0 8
2 3
5 3
6 0

Sample Output

0.8575
1.4142
0.9701

Hint

The result of the sample is shown as the following image:

Source

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