Kevin 最近剛學會了變異數（variance）的定義。對於一個長度為 $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$) — 測試案例的數量。接著是各個測試案例的描述。

每個測試案例的第一行包含三個整數 $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$ 個整數表示恰好執行 $p$ 次操作時，陣列 $a$ 可能的最小變異數乘以 $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 82623047140

說明

在第一個測試案例中：

• 對於 $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$。

In the second test case, some possible optimal choices are:

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

In the third test case, some possible optimal choices are:

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

In the eighth test case, the optimal choice for all $p$ is to perform the operation on the whole array $p$ times.