P10438 [JOIST 2024] 塔楼 / Tower

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

#### 样例解释 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 分）无额外约束。