Problem Description

IOI Tower is an extremely tall building equipped with a staircase for ascending. This staircase consists of $10^{100}$ steps, numbered from the bottom as step $0$, step $1$, and so on. JOI is currently at step $0$ and plans to climb the stairs. JOI can ascend the stairs using one of the following two methods, and descending is prohibited.

• Ascend one step. This action takes $A$ seconds.
• Jump from the current step to the $D$th step above, skipping the intermediate steps. This action takes $B$ seconds.

Currently, construction is underway at several locations on the stairs, and these steps cannot be stepped on. Specifically, there are $N$ construction sites, with the $i$-th site ($1 \leq i \leq N$) being from step $L_i$ to step $R_i$.

IOI Tower has $Q$ rooms, numbered from $1$ to $Q$. People can enter room $j$ ($1 \leq j \leq Q$) from step $X_j$ on the stairs. Therefore, JOI wants to determine if he can reach each room, and if possible, the shortest time in seconds required to reach them.

Given information about JOI, the construction sites, and the rooms, create a program to determine if JOI can reach room $j$ ($1 \leq j \leq Q$), and if possible, calculate the shortest 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, where the $j$-th line ($1 \leq j \leq Q$) contains the minimum number of seconds required for JOI to reach step $X_j$; if it is not possible to reach, output $-1$.

Sample Input and Output

Input Sample #1

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

Output Sample #1

120

Input Sample #2

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

Output Sample #2

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

Notes

Sample Explanation 1

JOI can reach step $13$ in $120$ seconds by following these steps:

• Ascend from step $0$ to step $1$. This operation takes $10$ seconds.
• Ascend from step $1$ to step $2$. This operation takes $10$ seconds.
• Ascend from step $2$ to step $3$. This operation takes $10$ seconds.
• Jump from step $3$ to step $7$, skipping intermediate steps. This operation takes $35$ seconds.
• Ascend from step $7$ to step $8$. This operation takes $10$ seconds.
• Ascend from step $8$ to step $9$. This operation takes $10$ seconds.
• Jump from step $9$ to step $13$, skipping intermediate steps. This operation takes $35$ seconds.

Since it is not possible 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.

见题面 Input 部分

见题面 Output 部分