{"raw_statement":[{"iden":"statement","content":"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 &lt; 0)$ with speed equal to $1$ unit per second. The trajectory of this light source is a straight segment connecting these two points.\n\nThere 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.\n\n<center>![image](https://espresso.codeforces.com/08043a138579f0966572e296482472676833f216.png)</center>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)$."},{"iden":"input","content":"First line contains three space separated integers $s_y$, $a$ and $b$ ($-10^9 \\le s_y &lt; 0$, $1 \\le a &lt; b \\le 10^9$) — corresponding coordinates of the light source.\n\nSecond line contains single integer $n$ ($1 \\le n \\le 2 \\cdot 10^5$) — number of segments in the fence.\n\nNext $n$ lines contain two integers per line: $l_i$ and $r_i$ ($1 \\le l_i &lt; r_i \\le 10^9$, $r_{i - 1} &lt; l_i$) — segments in the fence in increasing order. Segments don't intersect or touch each other.\n\nNext line contains single integer $q$ ($1 \\le q \\le 2 \\cdot 10^5$) — number of points to check.\n\nNext $q$ lines contain two integers per line: $x_i$ and $y_i$ ($1 \\le x_i, y_i \\le 10^9$) — points to process."},{"iden":"output","content":"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}$."},{"iden":"example","content":"Input\n\n\\-3 1 6\n2\n2 4\n6 7\n5\n3 1\n1 3\n6 1\n6 4\n7 6\n\nOutput\n\n5.000000000000000\n3.000000000000000\n0.000000000000000\n1.500000000000000\n2.000000000000000"},{"iden":"note","content":"*   The 1-st point is always in the shade;\n*   the 2-nd point is in the shade while light source is moving from $(3, -3)$ to $(6, -3)$;\n*   the 3-rd point is in the shade while light source is at point $(6, -3)$.\n*   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)$;\n*   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)$;"}],"translated_statement":[{"iden":"statement","content":"在平面上有一个光源。这个光源非常小，可以表示为一个点。光源从点 $(a, s_y)$ 移动到点 $(b, s_y)$（其中 $s_y < 0$），速度为每秒 1 单位。光源的轨迹是连接这两点的直线段。\n\n在 $O X$ 轴上有一个由 $n$ 个线段 $(l_i, r_i)$ 表示的围栏（因此每个线段的实际端点坐标为 $(l_i, 0)$ 和 $(r_i, 0)$）。点 $(x, y)$ 被称为 _在阴影中_，当且仅当连接 $(x, y)$ 与光源当前位置的线段与围栏的任意一个线段相交或相切。\n\n给定 $q$ 个点。对于每个点，计算当光源从 $(a, s_y)$ 移动到 $(b, s_y)$ 时，该点处于阴影中的总时间。\n\n第一行包含三个用空格分隔的整数 $s_y$、$a$ 和 $b$（$-10^9 \\leq s_y < 0$，$1 \\leq a < b \\leq 10^9$）——光源的对应坐标。\n\n第二行包含一个整数 $n$（$1 \\leq n \\leq 2 \\cdot 10^5$）——围栏的线段数量。\n\n接下来 $n$ 行，每行包含两个整数 $l_i$ 和 $r_i$（$1 \\leq l_i < r_i \\leq 10^9$，$r_{i -1} < l_i$）——按递增顺序排列的围栏线段。这些线段互不相交且不相触。\n\n下一行包含一个整数 $q$（$1 \\leq q \\leq 2 \\cdot 10^5$）——待检查的点的数量。\n\n接下来 $q$ 行，每行包含两个整数 $x_i$ 和 $y_i$（$1 \\leq x_i, y_i \\leq 10^9$）——待处理的点。\n\n输出 $q$ 行。第 $i$ 行应包含一个实数——第 $i$ 个点在光源从 $(a, s_y)$ 移动到 $(b, s_y)$ 过程中处于阴影中的总时间。若答案的绝对误差或相对误差不超过 $10^{-6}$，则认为正确。"},{"iden":"input","content":"第一行包含三个用空格分隔的整数 $s_y$、$a$ 和 $b$（$-10^9 \\leq s_y < 0$，$1 \\leq a < b \\leq 10^9$）——光源的对应坐标。第二行包含一个整数 $n$（$1 \\leq n \\leq 2 \\cdot 10^5$）——围栏的线段数量。接下来 $n$ 行，每行包含两个整数 $l_i$ 和 $r_i$（$1 \\leq l_i < r_i \\leq 10^9$，$r_{i -1} < l_i$）——按递增顺序排列的围栏线段。这些线段互不相交且不相触。下一行包含一个整数 $q$（$1 \\leq q \\leq 2 \\cdot 10^5$）——待检查的点的数量。接下来 $q$ 行，每行包含两个整数 $x_i$ 和 $y_i$（$1 \\leq x_i, y_i \\leq 10^9$）——待处理的点。"},{"iden":"output","content":"输出 $q$ 行。第 $i$ 行应包含一个实数——第 $i$ 个点在光源从 $(a, s_y)$ 移动到 $(b, s_y)$ 过程中处于阴影中的总时间。若答案的绝对误差或相对误差不超过 $10^{-6}$，则认为正确。"},{"iden":"note","content":"第一个点始终在阴影中；第二个点在光源从 $(3, -3)$ 移动到 $(6, -3)$ 时处于阴影中；第三个点在光源位于点 $(6, -3)$ 时处于阴影中；第四个点在光源从 $(1, -3)$ 移动到 $(2.5, -3)$ 以及位于点 $(6, -3)$ 时处于阴影中；第五个点在光源从 $(1, -3)$ 移动到 $(2.5, -3)$ 以及从 $(5.5, -3)$ 移动到 $(6, -3)$ 时处于阴影中；"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ s_y < 0 $ be the constant $ y $-coordinate of the light source.  \nLet $ a, b \\in \\mathbb{R} $ with $ a < b $, such that the light source moves along the line segment from $ (a, s_y) $ to $ (b, s_y) $ at speed 1 unit per second.  \nLet $ \\mathcal{F} = \\{ (l_i, r_i) \\}_{i=1}^n $ be a set of $ n $ disjoint closed intervals on the $ x $-axis, representing the fence segments, with $ l_i < r_i $ and $ r_{i-1} < l_i $ for all $ i \\geq 2 $.  \nLet $ P = \\{ (x_j, y_j) \\}_{j=1}^q $ be a set of $ q $ query points in the plane, with $ y_j > 0 $.  \n\nLet $ L(t) = (x(t), s_y) $ denote the position of the light source at time $ t \\in [0, T] $, where $ T = b - a $, and $ x(t) = a + t $.  \n\nA point $ p = (x_j, y_j) $ is **in the shade** at time $ t $ if the line segment from $ L(t) $ to $ p $ intersects or touches at least one fence segment $ (l_i, r_i) \\times \\{0\\} $.  \n\n**Constraints**  \n1. $ -10^9 \\leq s_y < 0 $  \n2. $ 1 \\leq a < b \\leq 10^9 $  \n3. $ 1 \\leq n \\leq 2 \\cdot 10^5 $, $ 1 \\leq l_i < r_i \\leq 10^9 $, $ r_{i-1} < l_i $  \n4. $ 1 \\leq q \\leq 2 \\cdot 10^5 $, $ 1 \\leq x_j, y_j \\leq 10^9 $  \n\n**Objective**  \nFor each query point $ p_j = (x_j, y_j) $, compute the total measure of time $ t \\in [0, b - a] $ during which the segment $ \\overline{L(t) p_j} $ intersects or touches at least one fence segment $ [l_i, r_i] \\times \\{0\\} $.  \n\nThat is, compute:  \n$$\nT_j = \\mu\\left( \\left\\{ t \\in [0, b - a] \\ \\middle|\\ \\exists i \\in \\{1, \\dots, n\\} \\text{ s.t. } \\overline{L(t) p_j} \\cap \\left( [l_i, r_i] \\times \\{0\\} \\right) \\neq \\emptyset \\right\\} \\right)\n$$  \nwhere $ \\mu $ denotes Lebesgue measure on $ \\mathbb{R} $.","simple_statement":null,"has_page_source":false}