IOI 塔是一座极高的塔，配有一条用于攀登的楼梯。这条楼梯由 $10^{100}$ 级台阶组成，从底部开始依次编号为第 0 级、第 1 级，以此类推。JOI-kun 目前位于第 0 级台阶，并打算攀登楼梯。JOI-kun 可以通过以下两种动作攀登楼梯。不允许向下走。

• 向上走 1 级台阶。此动作耗时 $A$ 秒。
• 从当前台阶跳跃至上方 $D$ 级台阶处，跳过中间的台阶。此动作耗时 $B$ 秒。

目前，楼梯的多个位置正在施工，处于施工状态的台阶不能踩踏。具体来说，共有 $N$ 处正在进行的施工，第 $i$ 处施工（$1 \le i \le N$）覆盖了第 $L_i, L_{i+1}, \dots, R_i$ 级台阶。

IOI 塔内有 $Q$ 个房间，编号为 1 到 $Q$。人们可以从楼梯的第 $X_j$ 级台阶进入第 $j$ 个房间（$1 \le j \le Q$）。因此，JOI-kun 决定确定他是否能到达每个房间，如果可以，计算到达该房间所需的最短时间。

给定关于 JOI-kun、施工情况和房间的信息，编写一个程序，确定 JOI-kun 是否能到达第 $X_j$ 级台阶（对于每个 $1 \le j \le Q$），如果可以，计算所需的最短时间。

输入格式

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

$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$

输出格式

输出 $Q$ 行到标准输出。第 $j$ 行（$1 \le j \le Q$）输出 JOI-kun 到达第 $X_j$ 级台阶所需的最短秒数；如果无法到达，则输出 -1。

数据范围

• $1 \le N \le 200\,000$
• $1 \le Q \le 200\,000$
• $1 \le D \le 10^{12}$
• $1 \le A \le 1\,000\,000$
• $1 \le B \le 1\,000\,000$
• $1 \le L_i \le R_i \le 10^{12}$ ($1 \le i \le N$)
• $R_i + 1 < L_{i+1}$ ($1 \le i \le N - 1$)
• $1 \le X_j \le 10^{12}$ ($1 \le j \le Q$)
• 所有输入值均为整数。

子任务

1. (5 分) $R_i \le 1\,000\,000$ ($1 \le i \le N$), $X_j \le 1\,000\,000$ ($1 \le j \le Q$)
2. (38 分) $N \le 2\,000$, $Q \le 2\,000$
3. (25 分) $A = 1$, $B = D$
4. (32 分) 无附加限制

样例

样例输入 1

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

样例输出 1

120

说明

JOI-kun 可以通过以下步骤在 120 秒内到达第 13 级台阶：

1. 从第 0 级走到第 1 级。耗时 10 秒。
2. 从第 1 级走到第 2 级。耗时 10 秒。
3. 从第 2 级走到第 3 级。耗时 10 秒。
4. 从第 3 级跳到第 7 级，跳过中间台阶。耗时 35 秒。
5. 从第 7 级走到第 8 级。耗时 10 秒。
6. 从第 8 级走到第 9 级。耗时 10 秒。
7. 从第 9 级跳到第 13 级，跳过中间台阶。耗时 35 秒。

由于无法在少于 120 秒的时间内到达第 13 级台阶，因此输出 120。

样例输入 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

样例输出 2

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