1016E · Rest In The Shades

Problem: There is a light source on the plane. This source is so small that it can be represented as point. The light source is moving from point $(a, s_y)$ to the $(b, s_y)$ $(s_y < 0)$ with speed equal to $1$ unit per second. The trajectory of this light source is a straight segment connecting these two points.

There is also a fence on $OX$ axis represented as $n$ segments $(l_i, r_i)$ (so the actual coordinates of endpoints of each segment are $(l_i, 0)$ and $(r_i, 0)$). The point $(x, y)$ is in the shade if segment connecting $(x,y)$ and the current position of the light source intersects or touches with any segment of the fence.

You are given $q$ points. For each point calculate total time of this point being in the shade, while the light source is moving from $(a, s_y)$ to the $(b, s_y)$.

Input Format: First line contains three space separated integers $s_y$, $a$ and $b$ ($-10^9 \le s_y < 0$, $1 \le a < b \le 10^9$) — corresponding coordinates of the light source.

Second line contains single integer $n$ ($1 \le n \le 2 \cdot 10^5$) — number of segments in the fence.

Next $n$ lines contain two integers per line: $l_i$ and $r_i$ ($1 \le l_i < r_i \le 10^9$, $r_{i - 1} < l_i$) — segments in the fence in increasing order. Segments don't intersect or touch each other.

Next line contains single integer $q$ ($1 \le q \le 2 \cdot 10^5$) — number of points to check.

Next $q$ lines contain two integers per line: $x_i$ and $y_i$ ($1 \le x_i, y_i \le 10^9$) — points to process.

Output Format: Print $q$ lines. The $i$-th line should contain one real number — total time of the $i$-th point being in the shade, while the light source is moving from $(a, s_y)$ to the $(b, s_y)$. The answer is considered as correct if its absolute of relative error doesn't exceed $10^{-6}$.

Note:

• The 1-st point is always in the shade;
• the 2-nd point is in the shade while light source is moving from $(3, -3)$ to $(6, -3)$;
• the 3-rd point is in the shade while light source is at point $(6, -3)$.
• the 4-th point is in the shade while light source is moving from $(1, -3)$ to $(2.5, -3)$ and at point $(6, -3)$;
• the 5-th point is in the shade while light source is moving from $(1, -3)$ to $(2.5, -3)$ and from $(5.5, -3)$ to $(6, -3)$;