CF2172B.Buses

There is a long straight road of length $\ell$ meters, where position $p$ denotes the point on the road that is $p$ meters away from the starting point. Along this road, there are $n$ buses moving in the positive direction, each traveling at the same constant speed of $x$ meters per minute. The $i$-th bus is currently at position $s_i$ and continues moving until it reaches its designated destination at position $t_i$. Once a bus reaches its destination, it ceases operation and all passengers must disembark.

There are also $m$ people who wish to reach the end of the road (position $\ell$). The current position of the $i$-th person is $p_i$, and each person can walk at a speed of at most $y$ meters per minute. If a person is at the same position as a bus, they may hop on the bus instantly. While riding a bus, they may hop off at any moment. The time required to board or leave a bus is considered negligible. Buses always move at a constant speed $x$ and never wait for passengers.

Your task is to determine the minimum possible time for each person to reach the end of the road.

Figure 1: An illustration for sample input 1.

有一条长度为 $\ell$ 米的笔直长路，其中位置 $p$ 表示距离起点 $p$ 米处的点。沿此道路有 $n$ 辆公交车正朝正方向行驶，每辆车均以恒定速度 $x$ 米/分钟运行。第 $i$ 辆车当前位于位置 $s_i$，并持续行驶直至抵达其指定终点位置 $t_i$。一旦某辆公交车到达其终点，即停止运行，所有乘客必须下车。

此外还有 $m$ 位行人希望抵达道路尽头（即位置 $\ell$）。第 $i$ 位行人当前位于位置 $p_i$，且每位行人步行速度至多为 $y$ 米/分钟。若某行人与某辆公交车处于同一位置，则可立即上车；在乘车过程中，亦可在任意时刻下车。上下车所需时间忽略不计。公交车始终以恒定速度 $x$ 行驶，且从不为乘客停留。

你的任务是求出每位行人抵达道路尽头所需的最短时间。

图 1：样例输入 1 的示意图。

The first line contains five integers $n$, $m$, $\ell$, $x$ and $y$, representing the number of buses, the number of people, the length of the road, the speed of the buses, and the walking speed of the people, respectively.

The $i$-th of the following $n$ lines contains two integers $s_i$ and $t_i$, representing the starting position and the destination position of the $i$-th bus.

The $i$-th of the following $m$ lines contains one integer $p_i$, representing the current position of the $i$-th person.

• $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$

第一行包含五个整数 $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$

Print $m$ lines. The $i$-th line contains a number which is the minimum time (in minutes) for the $i$-th person to reach the end of the road.

Your answer will be accepted if the 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 considered correct if $\frac{\left\vert a - b \right\vert}{\max(1, \left\vert b \right\vert)} \leq 10^{-6}$.

输出 $m$ 行。第 $i$ 行包含一个数字，表示第 $i$ 个人到达道路终点所需的最短时间（单位：分钟）。

若你的答案的绝对误差或相对误差不超过 $10^{-6}$，则该答案被接受。形式化地，设你的答案为 $a$，评测组的答案为 $b$，当且仅当 $\frac{\left\vert a - b \right\vert}{\max(1, \left\vert b \right\vert)} \leq 10^{-6}$ 时，你的答案被视为正确。

Explanation of Sample 1: A person initially at position $p = 3$ can reach the end of the road in $6.25$ minutes as follows:

• Wait for Bus 1 to arrive.
• Hop on the bus and ride it until it reaches its destination at position $t_1 = 5$.
• Get off the bus and walk the remaining distance to position $\ell = 10$.

As shown in Figure 1, the total time spent is $6.25$ minutes, which is the minimum possible.

样例 1 解释：一名初始位于位置 $p = 3$ 的人可按如下方式在 $6.25$ 分钟内抵达道路终点：

• 等待公交 1 到达；
• 上车并乘坐该公交车，直至其抵达目的地位置 $t_1 = 5$；
• 下车后步行剩余距离至位置 $\ell = 10$。

如图 1 所示，总耗时为 $6.25$ 分钟，此即可能的最短时间。