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

• Пусть $x = \frac{1}{n} \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, n \cdot m \le 2 \cdot 10^4, 1 \le k \le 10^5$) — длину массива $a$, максимальное количество операций и число, которое прибавляется к $a_i$ при каждой операции, соответственно.

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

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

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

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

Примеры

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

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

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

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 8262382623

Примечание

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

• Для $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: [1, 2, 2] \to [3, 2, 2]$;
• $p = 2: [1, 2, 2] \to [1, 4, 4] \to [3, 4, 4]$.

В третьем наборе входных данных некоторые возможные оптимальные варианты:

• $p = 1: [10, 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, 1, 1, 1, 1] \to [10, 1, 1, 1, 1, 10, 2, 2, 2, 2] \to [10, 2, 2, 2, 2, 10, 2, 2, 2, 2]$.

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