飞机上有光源。该源非常小,可以表示为点。光源从点 $$$(a, s_y)$$$ 移动到 $$$(b, s_y)$$$ $$$(s_y < 0)$$$,速度等于每秒 $$$1$$$ 单位。该光源的轨迹是连接这两点的直线段。
$$$OX$$$ 轴上还有一个栅栏,表示为 $$$n$$$ 段 $$$(l_i, r_i)$$$(因此每个段端点的实际坐标为 $$$(l_i, 0)$$$ 和 $$$(r_i, 0)$$$)。如果连接 $$$(x,y)$$$ 和光源当前位置的线段与围栏的任何线段相交或接触,则点 $$$(x, y)$$$ 位于阴影中。
您将获得 $$$q$$$ 积分。对于每个点,计算该点处于阴影中的总时间,同时光源从 $$$(a, s_y)$$$ 移动到 $$$(b, s_y)$$$。
输入
第一行包含三个空格分隔的整数 $$$s_y$$$、$$$a$$$ 和 $$$b$$$ ($$$-10^9 \le s_y < 0$$$, $$$1 \le a < b \le 10^9$$$) — 对应的光源坐标。
第二行包含单个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 围栏中的段数。
接下来的 $$$n$$$ 行每行包含两个整数:$$$l_i$$$ 和 $$$r_i$$$ ($$$1 \le l_i < r_i \le 10^9$$$, $$$r_{i - 1} < l_i$$$) — 栅栏中的段按升序排列。线段不相交或相互接触。
下一行包含单个整数 $$$q$$$ ($$$1 \le q \le 2 \cdot 10^5$$$) — 要检查的点数。
接下来的 $$$q$$$ 行每行包含两个整数:$$$x_i$$$ 和 $$$y_i$$$ ($$$1 \le x_i, y_i \le 10^9$$$) — 指向进程。
输出
打印 $$$q$$$ 行。第 $$$i$$$ 行应包含一个实数 - 当光源从 $$$(a, s_y)$$$ 移动到 $$$(b, s_y)$$$ 时,第 $$$i$$$ 点处于阴影中的总时间。如果相对误差的绝对值不超过 $$$10^{-6}$$$,则答案被认为是正确的。
示例
输入 #1
-3 1 6 2 2 4 6 7 5 3 1 1 3 6 1 6 4 7 6
输出 #1
5.000000000000000 3.000000000000000 0.000000000000000 1.500000000000000 2.000000000000000
注意
- 第一个点始终位于阴影中;
- 当光源从 $$$(3, -3)$$$ 移动到 $$$(6, -3)$$$ 时,第二个点位于阴影中;
- 第三个点位于阴影中,而光源位于点 $$$(6, -3)$$$。
- 当光源从 $$$(1, -3)$$$ 移动到 $$$(2.5, -3)$$$ 并在点 $$$(6, -3)$$$ 时,第 4 个点位于阴影中;
- 当光源从 $$$(1, -3)$$$ 移动到 $$$(2.5, -3)$$$ 以及从 $$$(5.5, -3)$$$ 移动到 $$$(6, -3)$$$ 时,第 5 个点位于阴影中;