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$)，表示测试用例的数量。接下来是各测试用例的描述。

每个测试用例的第一行包含三个整数 $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 8262300000

说明

在第一个测试用例中：

• 对于 $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$。

在第二个测试用例中，一些可能的最佳选择是：

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

在第三个测试用例中，一些可能的最佳选择是：

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

在第八个测试用例中，对于所有 $p$，最佳选择都是对整个数组执行 $p$ 次操作。