Kevin has recently learned the definition of variance. For an array $a$ of length $n$, the variance of $a$ is defined as follows:

• Let $x=\dfrac{1}{n}\displaystyle\sum_{i=1}^n a_i$, i.e., $x$ is the mean of the array $a$;
• Then, the variance of $a$ is $$ V(a)=\frac{1}{n}\sum_{i=1}^n(a_i-x)^2. $$

Now, Kevin gives you an array $a$ consisting of $n$ integers, as well as an integer $k$. You can perform the following operation on $a$:

• Select an interval $[l,r]$ ($1\le l\le r\le n$), then for each $l\le i\le r$, increase $a_i$ by $k$.

For each $1\le p\le m$, you have to find the minimum possible variance of $a$ after exactly $p$ operations are performed, independently for each $p$.

For simplicity, you only need to output the answers multiplied by $n^2$. It can be proven that the results are always integers.

Input

Each test contains multiple test cases. The first line of the input contains a single integer $t$ ($1\le t\le 100$) — the number of test cases. The description of test cases follows.

The first line of each test case contains three integers $n$, $m$, and $k$ ($1\le n,m\le 5000$, $\color{red}{n\cdot m\le 2\cdot 10^4}$, $1\le k\le 10^5$) — the length of the array $a$, the maximum number of operations, and the number you add to $a_i$ each time, respectively.

The second line contains $n$ integers $a_1,a_2,\ldots, a_n$ ($1\le a_i\le 10^5$) — the elements of the array $a$.

It is guaranteed that the sum of $n\cdot m$ over all tests does not exceed $2\cdot 10^4$.

Output

For each test case, output $m$ integers in a single line, the $p$-th integer denoting the minimum possible variance of $a$ when exactly $p$ operations are performed, multiplied by $n^2$.

Note

In the first test case:

• For $p = 1$, you can perform the operation on $[1, 1]$, changing $a$ from $[1, 2, 2]$ to $[2, 2, 2]$. Since all of the elements are equal, the variance is equal to $0$.
• For $p = 2$, you can perform the operation on $[1, 3]$ and then $[1, 1]$, changing $a$ from $[1, 2, 2]$ to $[2, 3, 3]$ to $[3, 3, 3]$. Since all of the elements are equal, the variance is equal to $0$.

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

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

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

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