Problem Description

The IOI Tower is an extremely tall tower with a staircase for going up. This staircase has $10^{100}$ steps, numbered starting from the bottom as step $0$, step $1$, and so on. JOI is currently at step $0$ and plans to climb the staircase. JOI can move upward in the following two ways, and moving downward is not allowed.

• Move up by $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.

Currently, some parts of the staircase are under construction, and steps under construction cannot be stepped on. More precisely, there are $N$ construction sections; in the $i$-th section ($1 \leq i \leq N$), the steps under construction are from $L_i$ to $R_i$.

The IOI Tower has $Q$ rooms, numbered from $1$ to $Q$. People can enter room $j$ from step $X_j$ of the staircase ($1 \leq j \leq Q$). Therefore, JOI decides to determine whether he can reach each room, and if possible, the minimum number of seconds needed.

Given the information about JOI, the construction, and the rooms, write a program that determines whether JOI can reach room $j$ ($1 \leq j \leq Q$), and if possible, computes the minimum time required.

Input Format

Read the following data from standard input.

• $N$ $Q$
• $D$ $A$ $B$
• $L_1$ $R_1$
• $L_2$ $R_2$
• ...
• $L_N$ $R_N$
• $X_1$
• $X_2$
• ...
• $X_Q$

Output Format

Output $Q$ lines. On the $j$-th line ($1 \leq j \leq Q$), output the minimum number of seconds needed for JOI to reach step $X_j$; if it is impossible to reach it, output $-1$.

3 1
4 10 35
4 5
10 12
14 14
13

120

5 10
10 1 9
7 11
25 32
37 38
43 44
50 52
6
12
18
24
30
36
42
48
54
60

6
11
17
22
-1
33
-1
44
-1
55

Hint

Sample Explanation 1

JOI can reach step $13$ of the staircase in $120$ seconds by the following steps:

• Move up from step $0$ to step $1$. This takes $10$ seconds.
• Move up from step $1$ to step $2$. This takes $10$ seconds.
• Move up from step $2$ to step $3$. This takes $10$ seconds.
• Jump from step $3$ to step $7$, skipping the steps in between. This takes $35$ seconds.
• Move up from step $7$ to step $8$. This takes $10$ seconds.
• Move up from step $8$ to step $9$. This takes $10$ seconds.
• Jump from step $9$ to step $13$, skipping the steps in between. This takes $35$ seconds.

Since it is impossible to reach step $13$ in less than $120$ seconds, the output is $120$.

This sample input satisfies the constraints of Subtasks $1, 2, 4$.

Sample Explanation 2

This sample input satisfies the constraints of Subtasks $1, 2, 4$.

Constraints

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

Subtasks

1. (5 points) $R_i \leq 1,000,000$ ($1 \leq i \leq N$), $X_j \leq 1,000,000$ ($1 \leq j \leq Q$).
2. (38 points) $N \leq 2,000$, $Q \leq 2,000$.
3. (25 points) $A = 1$, $B = D$.
4. (32 points) No additional constraints.

Translated by ChatGPT 5