D. Transportation Reform
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Buses on Leninsky Prospekt have started to run infrequently. Mark has become a victim of this transportation reform and is constantly late for school because of it. Nobody liked this, not even Mark, so he decided to optimize his route in other ways. Specifically, by using scooters.

It is known that Mark walks at a speed of $$$a$$$ m/s, while the scooter travels at a speed of $$$b$$$ m/s ($$$b \gt a$$$). Mark chooses a scooter as follows: the app suggests a circle centered at Mark's location with a minimum radius that contains at least one scooter, and marks all the scooters on this circle (there may be multiple scooters at some points). Mark selects one such scooter so that the total time walking to it and riding the scooter to school is minimized. If walking turns out to be no worse, Mark will walk; otherwise, he will ride that scooter.

Mark liked his method of traveling to school, so he decided to use it not only for school but also for other points in the city. Specifically, on $$$q$$$ days, he needs to get to the point ($$$x_i, y_i$$$). He lives at the point ($$$0, 0$$$). On each of the days, the circle and scooters will be the same (as companies return scooters to their places). There will always be $$$n$$$ scooters at the same distance from ($$$0, 0$$$). For each of the days, output the travel time from Mark's home to the respective point.

Input

The first line contains four integers $$$n,q,a,b$$$ ($$$1 \le n \le 10^5, 1 \le q \le 2 \cdot 10^5$$$, $$$1 \le a \lt b \le 10^9$$$) — the number of scooters that the app shows to Mark, the number of days Mark has to travel, the speed of walking, and the speed of riding the scooter, respectively.

The next $$$n$$$ lines contain two integers $$$x_j, y_j$$$ ($$$-10^9 \le x_j,y_j \le 10^9$$$) — the point where the $$$j$$$-th scooter is located.

The next $$$q$$$ lines contain two integers $$$x_i, y_i$$$ ($$$-10^9 \le x_i,y_i \le 10^9$$$) — the point Mark needs to reach on the $$$i$$$-th day.

Output

In $$$q$$$ lines, output the travel time for Mark from home to the respective point.

Your answer is considered correct if its absolute or relative error does not exceed $$$10^{-6}$$$. Formally, let your answer be $$$a$$$, and the jury's answer be $$$b$$$. Your answer is accepted if and only if $$$\frac{\left|a-b\right|}{\max(1, |b|)}$$$.

Scoring
№Additional ConstraintsPointsReq. GroupsComment
$$$n$$$$$$q$$$
$$$0$$$————Tests from the statement
$$$1$$$$$$n \le 1000$$$$$$q \le 1000$$$$$$29$$$$$$0$$$
$$$2$$$——$$$24$$$—$$$|x|, |y| \le 20$$$
$$$3$$$——$$$15$$$—$$$x,y \ge 0$$$
$$$4$$$——$$$13$$$$$$3$$$$$$y \ge 0$$$
$$$5$$$——$$$19$$$$$$0-4$$$—
Examples
Input
2 4 1 3
-3 4
4 3
0 -7
8 6
-6 8
0 15
Output
7.00000000000000000000
6.66666666666666666652
6.66666666666666666652
8.80058475033045972680
Input
3 4 1 2
0 10
0 10
0 -10
3 4
0 15
0 -15
20 0
Output
5.00000000000000000000
12.50000000000000000000
12.50000000000000000000
20.00000000000000000000