Kevin a récemment appris la définition de la variance. Pour un tableau $a$ de longueur $n$, la variance de $a$ est définie comme suit :

• Soit $x = \frac{1}{n} \sum_{i=1}^{n} a_i$, c'est-à-dire que $x$ est la moyenne du tableau $a$ ;
• Alors, la variance de $a$ est $$V(a) = \frac{1}{n} \sum_{i=1}^{n} (a_i - x)^2.$$

Maintenant, Kevin vous donne un tableau $a$ composé de $n$ entiers, ainsi qu'un entier $k$. Vous pouvez effectuer l'opération suivante sur $a$ :

• Sélectionner un intervalle $[l, r]$ ($1 \le l \le r \le n$), puis pour chaque $l \le i \le r$, augmenter $a_i$ de $k$.

Pour chaque $1 \le p \le m$, vous devez trouver la variance minimale possible de $a$ après avoir effectué exactement $p$ opérations, indépendamment pour chaque $p$.

Par souci de simplicité, vous n'avez qu'à afficher les réponses multipliées par $n^2$. Il peut être prouvé que les résultats sont toujours des entiers.

Entrée

Chaque test contient plusieurs cas de test. La première ligne de l'entrée contient un seul entier $t$ ($1 \le t \le 100$) — le nombre de cas de test. La description des cas de test suit.

La première ligne de chaque cas de test contient trois entiers $n$, $m$ et $k$ ($1 \le n, m \le 5000$, $n \cdot m \le 2 \cdot 10^4$, $1 \le k \le 10^5$) — la longueur du tableau $a$, le nombre maximum d'opérations, et le nombre que vous ajoutez à $a_i$ à chaque fois, respectivement.

La deuxième ligne contient $n$ entiers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^5$) — les éléments du tableau $a$.

Il est garanti que la somme de $n \cdot m$ sur tous les tests ne dépasse pas $2 \cdot 10^4$.

Sortie

Pour chaque cas de test, affichez $m$ entiers sur une seule ligne, le $p$-ième entier désignant la variance minimale possible de $a$ lorsque exactement $p$ opérations sont effectuées, multipliée par $n^2$.

Exemples

Entrée 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

Sortie 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 82623047140

Remarque

Dans le premier cas de test :

• Pour $p = 1$, vous pouvez effectuer l'opération sur $[1, 1]$, changeant $a$ de $[1, 2, 2]$ à $[2, 2, 2]$. Comme tous les éléments sont égaux, la variance est égale à 0.
• Pour $p = 2$, vous pouvez effectuer l'opération sur $[1, 3]$ puis sur $[1, 1]$, changeant $a$ de $[1, 2, 2]$ à $[2, 3, 3]$ puis à $[3, 3, 3]$. Comme tous les éléments sont égaux, la variance est égale à 0.

Dans le deuxième cas de test, quelques choix optimaux possibles sont :

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

Dans le troisième cas de test, quelques choix optimaux possibles sont :

• $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]$.

Dans le huitième cas de test, le choix optimal pour tout $p$ est d'effectuer l'opération sur tout le tableau $p$ fois.