题目描述

IOI Tower 是一座极其高的塔楼，配备了一条用于上升的楼梯。这个楼梯由 $10^{100}$ 个台阶组成，从底部开始依次编号为第 $0$ 级、第 $1$ 级，依此类推。JOI 君目前在第 $0$ 级，并打算爬楼梯。JOI 君可以通过以下两种方式上楼，禁止下楼。

• 上升 $1$ 级。这个动作需要 $A$ 秒。
• 从当前级别跳到上方 $D$ 级，跳过中间的台阶。这个动作需要 $B$ 秒。

目前，楼梯的几个位置正在进行施工，正在施工的台阶不能踩上去。具体来说，有 $N$ 处正在进行施工，第 $i$ 处施工（$1 \leq i \leq N$）正在进行的台阶为 $L_i$ 到 $R_i$。

IOI Tower 有 $Q$ 个房间，编号从 $1$ 到 $Q$。人们可以从楼梯的第 $X_j$ 级进入第 $j$ 个房间（$1 \leq j \leq Q$）。因此，JOI 君决定确定他是否可以到达每个房间，如果可能的话，以最短时间需要多少秒到达。

给出关于 JOI 君、施工和房间的信息，创建一个程序，确定 JOI 君是否可以到达第 $j$ 个房间（$1 \leq j \leq Q$），如果可能的话，计算需要的最短时间。

输入格式

从标准输入读取以下数据。

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

输出格式

输出 $Q$ 行，在第 $j$ 行（$1 \leq j \leq Q$）输出 JOI 君到达第 $X_j$ 级台阶所需的最少秒数；如果无法到达，则输出 $-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

提示

样例解释 1

JOI 君可以按照以下步骤在 $120$ 秒内到达楼梯的第 $13$ 阶：

• 从第 $0$ 阶到第 $1$ 阶上升。此操作需要 $10$ 秒。
• 从第 $1$ 阶到第 $2$ 阶上升。此操作需要 $10$ 秒。
• 从第 $2$ 阶到第 $3$ 阶上升。此操作需要 $10$ 秒。
• 从第 $3$ 阶跳到第 $7$ 阶，跳过中间的台阶。此操作需要 $35$ 秒。
• 从第 $7$ 阶到第 $8$ 阶上升。此操作需要 $10$ 秒。
• 从第 $8$ 阶到第 $9$ 阶上升。此操作需要 $10$ 秒。
• 从第 $9$ 阶跳到第 $13$ 阶，跳过中间的台阶。此操作需要 $35$ 秒。

由于无法在小于 $120$ 秒内到达第 $13$ 阶楼梯，输出为 $120$。

这个样例输入满足子任务 $1,2,4$ 的约束条件。

样例解释 2

这个样例输入满足子任务 $1,2,4$ 的约束条件。

约束条件

• $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$）
• 给定值均为整数。

子任务

1. （5 分）$R_i \leq 1,000,000$（$1 \leq i \leq N$），$X_j \leq 1,000,000$（$1 \leq j \leq Q$）
2. （38 分）$N \leq 2,000$，$Q \leq 2,000$
3. （25 分）$A = 1$，$B = D$
4. （32 分）无额外约束。