E. Epidemic Escape
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

There is a spaceship located at the origin of a 2-dimensional plane. There are $$$n$$$ infection points in the plane.

At time $$$t=0$$$ each infection will start spreading, creating a circle of radius $$$t$$$ centered around the infection point. Simultaneously, at time $$$t = 0$$$ the spaceship will also start moving with speed $$$1$$$, and with some shield level $$$k_j$$$. The spaceship will continue moving in a straight line until a moment comes when the number of infection circles that contain it is at least its shield value (at which point it will be consumed by the combined infection).

The spaceship's captain wants us to consider $$$q$$$ scenarios for how to steer the ship. In each potential scenario, the spaceship will move in the direction of the point $$$(x'_j, y'_j)$$$ with shield value $$$k_j$$$. Note that the given point is only to indicate direction, and the spaceship will continue moving even after passing $$$(x'_j, y'_j)$$$.

For each scenario, compute the time at which the spaceship will be destroyed, or report that the spaceship will survive forever.

Input

The first line of input contains a single integer $$$n$$$ ($$$1 \leq n \leq 10^5$$$).

The next $$$n$$$ lines of input contain two integers $$$x_i$$$ $$$y_i$$$, ($$$\left|x_i\right|, \left|y_i\right| \leq 10^8$$$).

The $$$n+2$$$-nd line of input contains a single integer — $$$q$$$ ($$$1 \leq q \leq 10^5)$$$.

The next $$$q$$$ lines of input contain three integers — $$$x'_j$$$, $$$y'_j$$$, $$$k_j$$$,($$$|x'_j|, |y'_j| \leq 10^8$$$, $$$1 \leq k_j \leq 5$$$, $$$\left|x'_i\right| + \left|y_i'\right| \neq 0$$$).

Output

The output contains $$$q$$$ lines of output — the time of destruction for each of the captain's plans (Your answer will be accepted if absolute or relative error is at most $$$10^{-6}$$$).

If the spaceship will survive forever, output $$$-1$$$ instead.

Examples
Input
5
5 -3
5 4
-6 2
-5 0
4 1
2
-3 -10 1
6 -9 1
Output
8.700255424092125
3.2260195622572536
Input
8
4 -1
4 -8
0 9
4 -7
-5 -2
5 -5
7 5
-9 2
10
4 -8 1
7 -7 5
-10 8 2
-9 9 2
4 -7 5
-1 -10 2
6 -3 2
2 -9 3
-10 -10 1
5 9 1
Output
3.1677629681247024
26.162950903902267
5.461488320163311
6.363961030678928
-1
5.2894082216425735
3.726779962499649
4.6097722286464435
2.9294423792014115
4.7617289402064875