P12503 「ROI 2025 Day1」索契游乐园

由于评测机性能差异，本题时限增加了 1 秒。

**译自 [ROI 2025](https://neerc.ifmo.ru/school/archive/2024-2025.html) Day1 T3.** ***[Сочи Парк ](https://neerc.ifmo.ru/school/archive/2024-2025/ru-olymp-roi-2025-day1.pdf)*** 索契游乐园新推出了一项刺激的游乐项目！沿着一条直线，摆放了 $n$ 个目标，每个目标的坐标为 $x_i$ $(1 \le i \le n)$。你的任务是以任意顺序击中所有这些目标。击中目标需要使用小球，假设你站在坐标 $x$ 的位置，想击中位于 $x_i$ 的目标，你需要消耗 $(x - x_i)^2$ 卡路里的能量。 你从坐标 $x_0$ 进入游乐项目。小球的补给点分布在入口处以及间隔 $d$ 的位置上，即坐标为 $x_0 + kd$ 的点（$k$ 为任意整数）。根据游乐项目的规则，你不能携带小球，只能从这些补给点投掷。 在比赛间隙，有 $m$ 位奥林匹克选手将体验这个项目。每位选手的体力不同，第 $j$ 位选手移动距离 $d$ 需要消耗 $t_j$ 卡路里的能量。 你的任务是计算每位选手完成所有目标所需的最少能量。

第一行包含一个整数 $n$ $(1 \leq n \leq 3 \cdot 10^{5})$，表示游乐项目中的目标数量。 第二行包含 $n$ 个整数 $x_{1}, x_{2}, \ldots, x_{n}$ $(0 \leq x_{i} \leq 10^{9})$，表示目标的坐标。 第三行包含两个整数 $x_{0}$ 和 $d$ $(0 \leq x_{0} \leq 10^{9}, 1 \leq d \leq 2 \cdot 10^{6})$，分别表示入口坐标和小球补给点之间的间距。 第四行包含一个整数 $m$ $(1 \leq m \leq 6 \cdot 10^{5})$，表示奥林匹克选手的数量。 接下来的 $m$ 行，每行包含一个整数 $t_j$ $(0 \leq t_j \leq 10^{8})$，表示第 $j$ 位选手移动距离 $d$ 所需的能量。

对每位选手，输出一个整数，表示他完成所有目标所需的最少能量。 在给定限制下，答案不会超过 64 位有符号整数的最大值。但中间计算可能需要使用 C++ 的 `__int128` 类型（仅 GNU C++ 编译器支持）、Java 的 `BigInteger` 或 Python 的 `int` 类型。

### 样例 1 解释 在第一个样例中，对于第 $2$ 位选手（$t_2 = 1$），最优的击中目标策略如下： 1. 从 $x_0 = 2$ 移动到 $x_0 - d = -1$，消耗 $t_2 = 1$ 卡路里。注意，选手坐标可以为负数。 2. 击中位于 $x_2 = 0$ 的目标，消耗 $(-1 - 0)^2 = 1$ 卡路里。 3. 移动到 $-1 + 2d = 5$，消耗 $2t_2 = 2$ 卡路里。 4. 击中位于 $x_1 = 4$ 的目标，消耗 $(5 - 4)^2 = 1$ 卡路里。 5. 移动到 $5 + d = 8$，消耗 $t_2 = 1$ 卡路里。 6. 击中位于 $x_3 = 7$ 的目标，消耗 $(8 - 7)^2 = 1$ 卡路里。 总能量消耗为 $1 + 1 + 2 + 1 + 1 + 1 = 7$ 卡路里。可以证明这是最小能量消耗。 对于第 $6$ 位选手（$t_6 = 23$），最优策略如下： 1. 击中位于 $x_2 = 0$ 的目标，消耗 $(2 - 0)^2 = 4$ 卡路里。 2. 移动到 $2 + d = 5$，消耗 $t_6 = 23$ 卡路里。 3. 击中位于 $x_3 = 7$ 的目标，消耗 $(7 - 5)^2 = 4$ 卡路里。 4. 击中位于 $x_1 = 4$ 的目标，消耗 $(5 - 4)^2 = 1$ 卡路里。 总能量消耗为 $4 + 23 + 4 + 1 = 32$ 卡路里。可以证明这是最小能量消耗。 ### 数据范围 详细子任务附加限制及分值如下表所示。其中子任务 $0$ 是样例。 | 子任务 | 分值 | 附加限制 | | :-: | :-: | :-: | | $1$ | $9$ | $m = 1$，$t_{1} = 0$ | | $2$ | $7$ | $n = 1$，$m \leq 10\,000$ | | $3$ | $8$ | $n = 2$，$m \leq 10\,000$，$x_{1} \leq x_{0} \leq x_{2}$ | | $4$ | $3$ | $n \leq 50$，$x_{0} = 0$，$m \leq 50$，$d \leq 50$，$x_{i} \leq 50$ | | $5$ | $2$ | $n \leq 50$，$x_{0} \leq 50$，$m \leq 50$，$d \leq 50$，$x_{i} \leq 50$ | | $6$ | $4$ | $x_{0} = 0$，$m \leq 10$，$x_{i} \leq 10^{6}$ | | $7$ | $2$ | $x_{0} \leq 10^{6}$，$m \leq 10$，$x_{i} \leq 10^{6}$ | | $8$ | $6$ | $x_{0} = 0$，$m \leq 10\,000$，$x_{i} \leq 10^{6}$ | | $9$ | $10$ | $x_{0} \leq 10^{6}$，$m \leq 10\,000$，$x_{i} \leq 10^{6}$ | | $10$ | $7$ | $x_{0} \leq 10^{6}$，$m \leq 10^{5}$，$x_{i} \leq 10^{6}$ | | $11$ | $2$ | $m \leq 10$ | $0,1,6,7$ | | $12$ | $12$ | $x_{0} = 0$，$m \leq 10^{5}$，$d = 1$ | | $13$ | $5$ | $m \leq 10^{5}$，$d = 1$ | | $14$ | $8$ | $x_{0} = 0$，$m \leq 10^{5}$ | | $15$ | $2$ | $m \leq 10^{5}$ | | $16$ | $1$ | $m \leq 2 \cdot 10^{5}$ | | $17$ | $3$ | $m \leq 3 \cdot 10^{5}$ | | $18$ | $9$ | 无附加限制 |