CF1644C.Increase Subarray Sums

You are given an array $a_1, a_2, \dots, a_n$, consisting of $n$ integers. You are also given an integer value $x$.

Let $f(k)$ be the maximum sum of a contiguous subarray of $a$ after applying the following operation: add $x$ to the elements on exactly $k$ distinct positions. An empty subarray should also be considered, it has sum $0$.

Note that the subarray doesn't have to include all of the increased elements.

Calculate the maximum value of $f(k)$ for all $k$ from $0$ to $n$ independently.

给你一个由 $n$ 个整数组成的数组 $a_1, a_2, \dots, a_n$，以及一个整数值 $x$。

定义 $f(k)$ 为：对数组 $a$ 执行如下操作后，其连续子数组的最大和——恰好将 $x$ 加到 $k$ 个互不相同的位置上的元素上。空子数组也需考虑，其和为 $0$。

注意：该连续子数组不必包含所有被增加过的元素。

请独立地计算 $k$ 从 $0$ 到 $n$ 的所有取值所对应的 $f(k)$ 的最大值。

The first line contains a single integer $t$ ($1 \le t \le 5000$) — the number of testcases.

The first line of the testcase contains two integers $n$ and $x$ ($1 \le n \le 5000$; $0 \le x \le 10^5$) — the number of elements in the array and the value to add.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($-10^5 \le a_i \le 10^5$).

The sum of $n$ over all testcases doesn't exceed $5000$.

第一行包含一个整数 $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$。

For each testcase, print $n + 1$ integers — the maximum value of $f(k)$ for all $k$ from $0$ to $n$ independently.

对于每个测试用例，输出 $n + 1$ 个整数——即对所有从 $0$ 到 $n$ 的 $k$，分别对应的 $f(k)$ 的最大值。

In the first testcase, it doesn't matter which elements you add $x$ to. The subarray with the maximum sum will always be the entire array. If you increase $k$ elements by $x$, $k \cdot x$ will be added to the sum.

In the second testcase:

• For $k = 0$, the empty subarray is the best option.
• For $k = 1$, it's optimal to increase the element at position $3$. The best sum becomes $-1 + 5 = 4$ for a subarray $[3, 3]$.
• For $k = 2$, it's optimal to increase the element at position $3$ and any other element. The best sum is still $4$ for a subarray $[3, 3]$.
• For $k = 3$, you have to increase all elements. The best sum becomes $(-2 + 5) + (-7 + 5) + (-1 + 5) = 5$ for a subarray $[1, 3]$.

在第一个测试用例中，将 $x$ 加到哪些元素上并不重要。和最大的子数组始终是整个数组。如果你将 $k$ 个元素各增加 $x$，则总和将增加 $k \cdot x$。

在第二个测试用例中：

• 当 $k = 0$ 时，空子数组是最优选择。
• 当 $k = 1$ 时，最优策略是将位置 $3$ 处的元素增加 $x$。此时最佳子数组和为 $-1 + 5 = 4$，对应子数组 $[3, 3]$。
• 当 $k = 2$ 时，最优策略是将位置 $3$ 处的元素以及任意另一个元素各增加 $x$。此时最佳子数组和仍为 $4$，对应子数组 $[3, 3]$。
• 当 $k = 3$ 时，必须将所有元素都增加 $x$。此时最佳子数组和为 $(-2 + 5) + (-7 + 5) + (-1 + 5) = 5$，对应子数组 $[1, 3]$。