Kevin niedawno poznał definicję wariancji. Dla tablicy $a$ o długości $n$, wariancję tablicy $a$ definiuje się następująco:

• Niech $x = \frac{1}{n} \sum_{i=1}^{n} a_i$, tzn. $x$ jest średnią arytmetyczną tablicy $a$;
• Wtedy wariancja $a$ wynosi: $$V(a) = \frac{1}{n} \sum_{i=1}^{n} (a_i - x)^2.$$

Kevin daje Ci tablicę $a$ składającą się z $n$ liczb całkowitych oraz liczbę całkowitą $k$. Możesz wykonać na tablicy $a$ następującą operację:

• Wybierz przedział $[l, r]$ ($1 \le l \le r \le n$), a następnie dla każdego $l \le i \le r$ zwiększ $a_i$ o $k$.

Dla każdego $1 \le p \le m$ musisz znaleźć minimalną możliwą wariancję tablicy $a$ po wykonaniu dokładnie $p$ operacji, niezależnie dla każdego $p$.

Dla uproszczenia należy wypisać wyniki pomnożone przez $n^2$. Można udowodnić, że wyniki są zawsze liczbami całkowitymi.

Wejście

Każdy zestaw danych zawiera wiele przypadków testowych. Pierwsza linia wejścia zawiera jedną liczbę całkowitą $t$ ($1 \le t \le 100$) — liczbę przypadków testowych. Następnie opisano poszczególne przypadki testowe.

Pierwsza linia każdego przypadku testowego zawiera trzy liczby całkowite $n, m$ oraz $k$ ($1 \le n, m \le 5000$, $n \cdot m \le 2 \cdot 10^4$, $1 \le k \le 10^5$) — długość tablicy $a$, maksymalną liczbę operacji oraz liczbę, o którą zwiększamy $a_i$ w każdej operacji.

Druga linia zawiera $n$ liczb całkowitych $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^5$) — elementy tablicy $a$.

Gwarantuje się, że suma $n \cdot m$ we wszystkich testach nie przekracza $2 \cdot 10^4$.

Wyjście

Dla każdego przypadku testowego wypisz $m$ liczb całkowitych w jednej linii, gdzie $p$-ta liczba oznacza minimalną możliwą wariancję tablicy $a$ po wykonaniu dokładnie $p$ operacji, pomnożoną przez $n^2$.

Przykład

Wejście 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

Wyjście 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 82623000000

Uwagi

W pierwszym przypadku testowym:

• Dla $p = 1$ można wykonać operację na $[1, 1]$, zmieniając $a$ z $[1, 2, 2]$ na $[2, 2, 2]$. Ponieważ wszystkie elementy są równe, wariancja wynosi $0$.
• Dla $p = 2$ można wykonać operację na $[1, 3]$, a następnie na $[1, 1]$, zmieniając $a$ z $[1, 2, 2]$ na $[2, 3, 3]$, a potem na $[3, 3, 3]$. Ponieważ wszystkie elementy są równe, wariancja wynosi $0$.

W drugim przypadku testowym przykładowe optymalne wybory to:

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

W trzecim przypadku testowym przykładowe optymalne wybory to:

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

W ósmym przypadku testowym optymalnym wyborem dla każdego $p$ jest wykonanie operacji na całej tablicy $p$ razy.