Сочи Парк

В Сочи Парке открылся новый аттракцион. Вдоль прямой расположены $n$ целей, координата $i$-й цели равна $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$-му участнику олимпиады для перемещения между двумя соседними местами нахождения запасов мячиков.

Для каждого участника олимпиады выведите одно целое число --- минимальное количество, необходимое ему для перемещения и поражения всех целей.

При данных ограничениях ответ не превосходит максимального значения 64-битного знакового типа данных. Однако для промежуточных вычислений может понадобиться тип данных __int128 в C++ (поддерживается только в компиляторе GNU C++), BigInteger в Java, int в Python.

В первом тесте для второго участника ($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 + 2 + 1 + 1 + 1 + 1 = 7$ калорий. Можно показать, что это минимальное количество энергии.

Для шестого участника ($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$ калории. Можно показать, что это минимальное количество энергии.