Tower

The IOI Tower is an extremely tall tower with a staircase for climbing. The staircase has $10^{100}$ steps, numbered from the bottom as step $0$, step $1$, and so on. JOI-kun is on step $0$ and wants to climb the staircase. JOI-kun can ascend by taking one of the following 2 actions. Descending is not allowed.

• Ascend 1 step. This action takes $A$ seconds.
• Jump from the current step to the step $D$ steps above, skipping the steps in between. This action takes $B$ seconds.

Some steps are under construction and cannot be stepped on. There are $N$ constructions, and the $i$-th construction covers steps $L_i, L_{i+1}, \dots, R_i$.

The IOI Tower has $Q$ rooms numbered from $1$ to $Q$. Room $j$ can be entered from step $X_j$. For each room, determine whether JOI-kun can reach step $X_j$ and, if so, the minimum time needed to get there.

The first line contains $N$ and $Q$. The second line contains $D$, $A$, and $B$. Each of the next $N$ lines contains $L_i$ and $R_i$. Each of the next $Q$ lines contains $X_j$.

Output $Q$ lines. On line $j$, print the minimum number of seconds needed to reach step $X_j$. If step $X_j$ is unreachable, print -1.

• $1 \le N \le 200\,000$
• $1 \le Q \le 200\,000$
• $1 \le D \le 10^{12}$
• $1 \le A \le 1\,000\,000$
• $1 \le B \le 1\,000\,000$
• $1 \le L_i \le R_i \le 10^{12}$ ($1 \le i \le N$)
• $R_i + 1 < L_{i+1}$ ($1 \le i \le N - 1$)
• $1 \le X_j \le 10^{12}$ ($1 \le j \le Q$)
• All given values are integers.