有一条长 $$$\ell$$$ 米的长直路,其中 仓位 $$$p$$$ 表示道路上距离起点 $$$p$$$ 米的点。沿着这条路,有 $$$n$$$ 辆公交车正向行驶,每辆公交车都在 同样的恒速 每分钟 $$$x$$$ 米。第 $$$i$$$ 辆公交车当前位于位置 $$$s_i$$$ 并继续行驶,直到到达位于位置 $$$t_i$$$ 的指定目的地。一旦公共汽车到达目的地,它就会停止运营,所有乘客都必须下车。
还有$$$m$$$ 人希望到达路的尽头(位置$$$\ell$$$)。第 $$$i$$$ 人的当前位置为 $$$p_i$$$,每个人可以以 最多 $$$y$$$ 米每分钟。如果一个人与公交车处于同一位置,他们可能会立即跳上公交车。乘坐公共汽车时,他们可能随时下车。登上或离开公共汽车所需的时间被认为可以忽略不计。公共汽车总是以匀速 $$$x$$$ 行驶,并且从不等待乘客。
你的任务是确定每个人到达路尽头的最短可能时间。
图 1:示例输入 1 的图示。 输入
第一行包含五个整数$$$n$$$、$$$m$$$、$$$\ell$$$、$$$x$$$和$$$y$$$,分别代表公交车数量、人数、道路长度、公交车速度和人的步行速度。
以下$$$n$$$行中的第$$$i$$$行包含两个整数$$$s_i$$$和$$$t_i$$$,分别代表第$$$i$$$行的起始位置和目的地位置。
以下$$$m$$$行中的第$$$i$$$行包含一个整数$$$p_i$$$,代表第$$$i$$$个人的当前位置。
- $$$1 \leq n \leq 2 \times 10^5$$$
- $$$1 \leq m \leq 2 \times 10^5$$$
- $$$1 \leq \ell \leq 10^9$$$
- $$$1 \leq y \lt x \leq 10^6$$$
- $$$0 \leq s_i \lt t_i \leq \ell$$$
- $$$0 \leq p_i \leq \ell$$$
输出
打印 $$$m$$$ 行。第 $$$i$$$ 行包含一个数字,该数字是第 $$$i$$$ 人到达路尽头的最短时间(以分钟为单位)。
如果绝对或相对误差不超过 $$$10^{-6}$$$,您的答案将被接受。正式来说,让您的答案为$$$a$$$,陪审团的答案为$$$b$$$。如果 $$$\frac{\left\vert a - b \right\vert}{\max(1, \left\vert b \right\vert)} \leq 10^{-6}$$$,则认为您的答案是正确的。
示例
输入复制
3 3 10 4 1 0 5 2 4 7 9 3 8 5
输出复制
6.25 1.5 5
输入复制
1 3 100 100 1 1 2 0 1 2
输出复制
100 98.01 98
注意
样本1说明: 最初位于 $$$p = 3$$$ 位置的人可以在 $$$6.25$$$ 分钟内到达道路尽头,如下所示:
- 等待1路公交车到达。
- 跳上巴士并乘坐它,直到到达目的地 $$$t_1 = 5$$$ 位置。
- 下车并步行剩余距离到位置$$$\ell = 10$$$。
如图 1 所示,花费的总时间为 $$$6.25$$$ 分钟,这是可能的最小值。