Kevin は最近、分散の定義を学びました。長さ $n$ の配列 $a$ に対して、その分散は以下のように定義されます。

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

さて、Kevin はあなたに $n$ 個の整数からなる配列 $a$ と整数 $k$ を与えます。あなたは $a$ に対して以下の操作を行うことができます。

• 区間 $[l, r]$ ($1 \le l \le r \le n$) を選択し、$l \le i \le r$ を満たす各 $a_i$ に $k$ を加算する。

各 $1 \le p \le m$ について、ちょうど $p$ 回の操作を行った後の $a$ の分散の最小値を求めてください。各 $p$ は独立して考えます。

単純化のため、答えを $n^2$ 倍して出力してください。結果は常に整数になることが証明できます。

入力

各テストケースは複数のテストケースを含みます。入力の最初の行には、テストケースの数 $t$ ($1 \le t \le 100$) が含まれます。続いて各テストケースの説明が続きます。

各テストケースの最初の行には、3つの整数 $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$ に加算する値を表します。

2行目には、$n$ 個の整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^5$) が含まれます。これらは配列 $a$ の要素です。

すべてのテストケースにおける $n \cdot m$ の総和は $2 \cdot 10^4$ を超えないことが保証されています。

出力

各テストケースについて、$m$ 個の整数を1行に出力してください。$p$ 番目の整数は、ちょうど $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 82623000000

注記

最初のテストケースについて：

• $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$ です。

2番目のテストケースにおいて、考えられる最適な選択肢の一部は以下の通りです：

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

3番目のテストケースにおいて、考えられる最適な選択肢の一部は以下の通りです：

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

8番目のテストケースにおいて、すべての $p$ に対する最適な選択は、配列全体に対して $p$ 回操作を行うことです。