Kevin ha aprendido recientemente la definición de varianza. Para un arreglo $a$ de longitud $n$, la varianza de $a$ se define de la siguiente manera:
- Sea $x = \frac{1}{n} \sum_{i=1}^{n} a_i$, es decir, $x$ es la media del arreglo $a$;
- Entonces, la varianza de $a$ es $$V(a) = \frac{1}{n} \sum_{i=1}^{n} (a_i - x)^2.$$
Ahora, Kevin te da un arreglo $a$ que consiste en $n$ enteros, así como un entero $k$. Puedes realizar la siguiente operación en $a$:
- Seleccionar un intervalo $[l, r]$ ($1 \le l \le r \le n$), luego para cada $l \le i \le r$, aumentar $a_i$ en $k$.
Para cada $1 \le p \le m$, debes encontrar la varianza mínima posible de $a$ después de realizar exactamente $p$ operaciones, independientemente para cada $p$.
Por simplicidad, solo necesitas imprimir las respuestas multiplicadas por $n^2$. Se puede demostrar que los resultados son siempre enteros.
Entrada
Cada prueba contiene múltiples casos de prueba. La primera línea de la entrada contiene un único entero $t$ ($1 \le t \le 100$) — el número de casos de prueba. La descripción de los casos de prueba sigue.
La primera línea de cada caso de prueba contiene tres enteros $n$, $m$ y $k$ ($1 \le n, m \le 5000$, $n \cdot m \le 2 \cdot 10^4$, $1 \le k \le 10^5$) — la longitud del arreglo $a$, el número máximo de operaciones y el número que sumas a $a_i$ cada vez, respectivamente.
La segunda línea contiene $n$ enteros $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^5$) — los elementos del arreglo $a$.
Se garantiza que la suma de $n \cdot m$ en todas las pruebas no excede $2 \cdot 10^4$.
Salida
Para cada caso de prueba, imprime $m$ enteros en una sola línea, donde el $p$-ésimo entero denota la varianza mínima posible de $a$ cuando se realizan exactamente $p$ operaciones, multiplicada por $n^2$.
Ejemplos
Entrada 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
Salida 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
Nota
En el primer caso de prueba:
- Para $p = 1$, puedes realizar la operación en $[1, 1]$, cambiando $a$ de $[1, 2, 2]$ a $[2, 2, 2]$. Dado que todos los elementos son iguales, la varianza es igual a 0.
- Para $p = 2$, puedes realizar la operación en $[1, 3]$ y luego en $[1, 1]$, cambiando $a$ de $[1, 2, 2]$ a $[2, 3, 3]$ y luego a $[3, 3, 3]$. Dado que todos los elementos son iguales, la varianza es igual a 0.
En el segundo caso de prueba, algunas opciones óptimas posibles son:
- $p = 1$: $[1, 2, 2] \to [3, 2, 2]$;
- $p = 2$: $[1, 2, 2] \to [1, 4, 4] \to [3, 4, 4]$.
En el tercer caso de prueba, algunas opciones óptimas posibles son:
- $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]$.
En el octavo caso de prueba, la opción óptima para todo $p$ es realizar la operación en todo el arreglo $p$ veces.