시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 2048 MB35338.571%

문제

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

서브태스크

번호배점제한
19

$m = 1$, $t_{1} = 0$

27

$n = 1$, $m \leq 10\,000$

38

$n = 2$, $m \leq 10\,000$, $x_{1} \leq x_{0} \leq x_{2}$

43

$n \leq 50$, $x_{0} = 0$, $m \leq 50$, $d \leq 50$, $x_{i} \leq 50$

52

$n \leq 50$, $x_{0} \leq 50$, $m \leq 50$, $d \leq 50$, $x_{i} \leq 50$

64

$x_{0} = 0$, $m \leq 10$, $x_{i} \leq 10^{6}$

72

$x_{0} \leq 10^{6}$, $m \leq 10$, $x_{i} \leq 10^{6}$

86

$x_{0} = 0$, $m \leq 10\,000$, $x_{i} \leq 10^{6}$

910

$x_{0} \leq 10^{6}$, $m \leq 10\,000$, $x_{i} \leq 10^{6}$

107

$x_{0} \leq 10^{6}$, $m \leq 10^{5}$, $x_{i} \leq 10^{6}$

112

$m \leq 10$

1212

$x_{0} = 0$, $m \leq 10^{5}$, $d = 1$

135

$m \leq 10^{5}$, $d = 1$

148

$x_{0} = 0$, $m \leq 10^{5}$

152

$m \leq 10^{5}$

161

$m \leq 2 \cdot 10^{5}$

173

$m \leq 3 \cdot 10^{5}$

189

예제 입력 1

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

예제 출력 1

3
7
10
12
13
32
3

예제 입력 2

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

예제 출력 2

49
355
525
3378
93311

예제 입력 3

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

예제 출력 3

49597
91
159
1043
703

노트

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

채점 및 기타 정보

  • 예제는 채점하지 않는다.
  • 이 문제의 채점 우선 순위는 2이다.