C. Увеличь суммы подотрезков
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Задан массив $$$a_1, a_2, \dots, a_n$$$, состоящий из $$$n$$$ целых чисел. Также дано целое число $$$x$$$.

Пусть $$$f(k)$$$ будет равно максимальной сумме последовательного подмассива $$$a$$$ после применения следующей операции: прибавить $$$x$$$ к элементам на ровно $$$k$$$ различных позициях. Пустой подмассив тоже рассматривается, его сумма равна $$$0$$$.

Обратите внимание, что подмассив не обязан включать в себя все увеличенные элементы.

Посчитайте максимальное значение $$$f(k)$$$ для каждого $$$k$$$ от $$$0$$$ до $$$n$$$ независимо.

Входные данные

В первой строке записано одно целое число $$$t$$$ ($$$1 \le t \le 5000$$$) — количество наборов входных данных.

В первой строке каждого набора записано два целых числа $$$n$$$ и $$$x$$$ ($$$1 \le n \le 5000$$$; $$$0 \le x \le 10^5$$$) — количество элементов массива и значение для прибавления.

Во второй строке записаны $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$-10^5 \le a_i \le 10^5$$$).

Сумма $$$n$$$ по всем наборам целых чисел не превосходят $$$5000$$$.

Выходные данные

На каждый набор входных данных выведите $$$n + 1$$$ целое число — максимальное значение $$$f(k)$$$ для каждого $$$k$$$ от $$$0$$$ до $$$n$$$ независимо.

Пример
Входные данные
3
4 2
4 1 3 2
3 5
-2 -7 -1
10 2
-6 -1 -2 4 -6 -1 -4 4 -5 -4
Выходные данные
10 12 14 16 18
0 4 4 5
4 6 6 7 7 7 7 8 8 8 8
Примечание

В первом наборе не важно, к каким элементам прибавлять $$$x$$$. Подотрезок с максимальной суммой всегда будет целым массивом. Если увеличить $$$k$$$ элементов на $$$x$$$, к сумме прибавится $$$k \cdot x$$$.

Во втором наборе:

  • Для $$$k = 0$$$ пустой подмассив — это лучший вариант.
  • Для $$$k = 1$$$ наиболее выгодно увеличить элемент на позиции $$$3$$$. Лучшая сумма становится $$$-1 + 5 = 4$$$ для подмассива $$$[3, 3]$$$.
  • Для $$$k = 2$$$ наиболее выгодно увеличить элемент на позиции $$$3$$$ и любой другой элемент. Лучшая сумма останется $$$4$$$ для подотрезка $$$[3, 3]$$$.
  • Для $$$k = 3$$$ необходимо увеличить все элементы. Лучшая сумма становится $$$(-2 + 5) + (-7 + 5) + (-1 + 5) = 5$$$ для подотрезка $$$[1, 3]$$$.