Kevin 最近学习了方差的定义。对于长度为 $$$n$$$ 的数组 $$$a$$$,$$$a$$$ 的方差定义如下:
- 让$$$x=\dfrac{1}{n}\displaystyle\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\let t\le 100$$$) - 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含三个整数 $$$n$$$、$$$m$$$ 和 $$$k$$$ ($$$1\le n,m\le 5000$$$, $$$\color{red}{n\cdot m\le 2\cdot 10^4}$$$, $$$1\le k\le 10^5$$$) —分别是数组 $$$a$$$ 的长度、最大操作次数以及每次添加到 $$$a_i$$$ 的数字。
第二行包含 $$$n$$$ 整数 $$$a_1,a_2,\ldots, 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 82623647140
注意
在第一个测试用例中:
- 对于$$$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]\到 [3,2,2]$$$;
- $$$p=2$$$: $$$[1,\underline{2,2}] \ 到 [\underline{1,}\,4,4] \ 到 [3,4,4]$$$。
在第三个测试用例中,一些可能的最佳选择是:
- $$$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,\下划线{1,1,1,1}]\到[10,\下划线{1,1,1,1},10,2,2,2,2]\到[10,2,2,2,2,10,2,2,2,2]$$$。
在第八个测试用例中,所有 $$$p$$$ 的最佳选择是对整个数组执行操作 $$$p$$$ 次。