Кевин недавно узнал определение дисперсии. Для массива \(a\) длины \(n\) дисперсия \(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. \(\)
Теперь Кевин даст вам массив \(a\), состоящий из \(n\) целых чисел, а также целое число \(k\). Вы можете выполнять следующую операцию над \(a\):
- Выберите отрезок \([l,r]\) (\(1\le l\le r\le n\)), затем для каждого \(l\le i\le r\) увеличьте \(a_i\) на \(k\).
Для каждого \(1\le p\le m\) вам нужно найти минимально возможную дисперсию \(a\) после выполнения ровно \(p\) операций, независимо для каждого \(p\).
Для простоты вам нужно только вывести ответы, домноженные на \(n^2\). Можно доказать, что результаты всегда являются целыми числами.
Выходные данные
Для каждого теста выведите \(m\) целых чисел в одной строке, где \(p\)-е целое число обозначает минимально возможную дисперсию \(a\) после выполнении ровно \(p\) операций, домноженную на \(n^2\).
Примечание
В первом наборе входных данных:
- Для \(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\): \([\underline{1,}\,2,2]\to [3,2,2]\);
- \(p=2\): \([1,\underline{2,2}] \to [\underline{1,}\,4,4] \to [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,\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]\).
В восьмом наборе входных данных для всех \(p\) оптимально выполнить операцию над всем массивом \(p\) раз.
Примеры
| № | Входные данные | Выходные данные |
|
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
|
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
|