题目背景

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

题目描述

译自 ROI 2025 Day1 T3. Сочи Парк

索契游乐园新推出了一项刺激的游乐项目！沿着一条直线，摆放了 $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 类型。

3
4 0 7
2 3
7
0
1
2
3
4
23
25

3
7
10
12
13
32
33

4
30 239 57 179
0 7
5
1
10
15
100
100000

49
355
525
3378
93311

4
100 2 101 666
9 10
5
777
1
2
15
10

49597
91
159
1043
703

提示

样例 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$
$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$	无附加限制