31734번 - Tower 서브태스크다국어

The IOI Tower is an extremely tall tower equipped with a staircase for ascending. This staircase consists of $10^{100}$ steps, numbered sequentially from the bottom as step $0$, step $1$, and so on. JOI-kun is currently on step $0$ and intends to climb the staircase. JOI-kun can ascend the staircase by taking the following $2$ types of actions. Descending the staircase is not permitted.

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

Currently, construction is ongoing at several locations on the staircase, and steps undergoing construction cannot be stepped on. Specifically, there are $N$ ongoing constructions, and the $i$-th construction ($1 ≤ i ≤ N$) is being carried out at steps $L_i , L_{i+1}, \dots , R_i$.

The IOI Tower has $Q$ rooms numbered from $1$ to $Q$. One can enter room $j$ ($1 ≤ j ≤ Q$) from step $X_j$ of the staircase. Therefore, JOI-kun has decided to determine whether he can reach each room and, if possible, how many seconds it will take to reach there in the minimum time.

Given the information about JOI-kun, constructions, and rooms, create a program that determines whether JOI-kun can reach step $X_j$ for each $j$ ($1 ≤ j ≤ Q$) and, if possible, calculates the minimum time it takes.

Read the following data from the standard input.

$N$ $Q$

$D$ $A$ $B$

$L_1$ $R_1$

$L_2$ $R_2$

$\vdots$

$L_N$ $R_N$

$X_1$

$X_2$

$\vdots$

$X_Q$

Output $Q$ lines to the standard output. On the $j$-th line ($1 ≤ j ≤ Q$), output the minimum number of seconds it takes if JOI-kun can reach step $X_j$; otherwise, output -1.

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