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.
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$$$).
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.
5 5 -3 5 4 -6 2 -5 0 4 1 2 -3 -10 1 6 -9 1
8.700255424092125 3.2260195622572536
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
3.1677629681247024 26.162950903902267 5.461488320163311 6.363961030678928 -1 5.2894082216425735 3.726779962499649 4.6097722286464435 2.9294423792014115 4.7617289402064875
| Name |
|---|


