I. Вызов дисперсии
ограничение по времени на тест
6 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Кевин недавно узнал определение дисперсии. Для массива $$$a$$$ длины $$$n$$$ дисперсия $$$a$$$ определяется следующим образом:

  • Пусть $$$x=\dfrac{1}{n}\displaystyle\sum_{i=1}^n a_i$$$, т.е. $$$x$$$ — это среднее арифметическое массива $$$a$$$;
  • Тогда дисперсия $$$a$$$ равна $$$$$$ V(a)=\frac{1}{n}\sum_{i=1}^n(a_i-x)^2. $$$$$$

Теперь Кевин даст вам массив $$$a$$$, состоящий из $$$n$$$ целых чисел, а также целое число $$$k$$$. Вы можете выполнять следующую операцию над $$$a$$$:

  • Выберите отрезок $$$[l,r]$$$ ($$$1\le l\le r\le n$$$), затем для каждого $$$l\le i\le r$$$ увеличьте $$$a_i$$$ на $$$k$$$.

Для каждого $$$1\le p\le m$$$ вам нужно найти минимально возможную дисперсию $$$a$$$ после выполнения ровно $$$p$$$ операций, независимо для каждого $$$p$$$.

Для простоты вам нужно только вывести ответы, домноженные на $$$n^2$$$. Можно доказать, что результаты всегда являются целыми числами.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1\le t\le 100$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит три целых числа $$$n$$$, $$$m$$$ и $$$k$$$ ($$$1\le n,m\le 5000$$$, $$$\color{red}{n\cdot m\le 2\cdot 10^4}$$$, $$$1\le k\le 10^5$$$) — длину массива $$$a$$$, максимальное количество операций и число, которое добавляется к $$$a_i$$$ в операции из условия.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1,a_2,\ldots, a_n$$$ ($$$1\le a_i\le 10^5$$$) — элементы массива $$$a$$$.

Гарантируется, что сумма $$$n\cdot m$$$ по всем тестам не превышает $$$2\cdot 10^4$$$.

Выходные данные

Для каждого теста выведите $$$m$$$ целых чисел в одной строке, где $$$p$$$-е целое число обозначает минимально возможную дисперсию $$$a$$$ после выполнении ровно $$$p$$$ операций, домноженную на $$$n^2$$$.

Пример
Входные данные
9
3 2 1
1 2 2
3 2 2
1 2 2
10 2 1
10 1 1 1 1 10 1 1 1 1
6 8 2
1 1 4 5 1 3
8 8 7
20 43 24 2 4 3 20 43
8 8 3
20 43 24 2 4 3 20 43
10 12 1
5 3 3 5 4 1 8 1 1 1
13 10 100000
1 2 3 4 5 6 7 8 9 10 11 5 4
10 5 10000
2308 9982 4435 3310 100000 9 7 8100 1919 100000
Выходные данные
0 0
2 2
1161 1024
53 21 21 5 5 5 5 5
10608 6912 4448 3104 1991 1312 535 304
13248 11184 9375 7815 6447 5319 4383 3687
385 316 269 224 181 156 124 101 80 56 41 29
1486 1486 1486 1486 1486 1486 1486 1486 1486 1486
134618047140 119919447140 107020847140 93922247140 82623647140
Примечание

В первом наборе входных данных:

  • Для $$$p = 1$$$ вы можете выполнить операцию на $$$[1, 1]$$$, изменив $$$a$$$ с $$$[1, 2, 2]$$$ на $$$[2, 2, 2]$$$. Поскольку все элементы равны, дисперсия равна $$$0$$$.
  • Для $$$p = 2$$$ вы можете выполнить операцию на $$$[1, 3]$$$, а затем на $$$[1, 1]$$$, изменив $$$a$$$ с $$$[1, 2, 2]$$$ на $$$[2, 3, 3]$$$, а затем на $$$[3, 3, 3]$$$. Поскольку все элементы равны, дисперсия равна $$$0$$$.

Во втором наборе входных данных:

  • $$$p=1$$$: $$$[\underline{1,}\,2,2]\to [3,2,2]$$$;
  • $$$p=2$$$: $$$[1,\underline{2,2}] \to [\underline{1,}\,4,4] \to [3,4,4]$$$.

В третьем наборе входных данных:

  • $$$p=1$$$: $$$[10,\underline{1,1,1,1,10,1,1,1,1}]\to[10,2,2,2,2,11,2,2,2,2]$$$;
  • $$$p=2$$$: $$$[10,1,1,1,1,10,\underline{1,1,1,1}] \to [10,\underline{1,1,1,1},10,2,2,2,2] \to [10,2,2,2,2,10,2,2,2,2]$$$.

В восьмом наборе входных данных для всех $$$p$$$ оптимально выполнить операцию над всем массивом $$$p$$$ раз.