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.

서브태스크

힌트