给定一个数组 $$$a_1, a_2, \dots, a_n$$$,由 $$$n$$$ 整数组成。您还会获得一个整数值 $$$x$$$。
应用以下操作后,令 $$$f(k)$$$ 为 $$$a$$$ 的连续子数组的最大总和:将 $$$x$$$ 添加到恰好 $$$k$$$ 不同位置上的元素。还应该考虑一个空子数组,它的总和为 $$$0$$$。
请注意,子数组不必包含所有增加的元素。
独立计算从 $$$0$$$ 到 $$$n$$$ 的所有 $$$k$$$ 的 $$$f(k)$$$ 最大值。
输入
第一行包含一个整数 $$$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$$$ 整数 - 从 $$$0$$$ 到 $$$n$$$ 的所有 $$$k$$$ 的 $$$f(k)$$$ 的最大值。
示例
输入 #1
3 4 2 4 1 3 2 3 5 -2 -7 -1 10 2 -6 -1 -2 4 -6 -1 -4 4 -5 -4
输出 #1
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$$$ 处的元素。对于子数组 $$$[3, 3]$$$,最佳总和变为 $$$-1 + 5 = 4$$$。
- 对于 $$$k = 2$$$,最好增加位置 $$$3$$$ 处的元素以及任何其他元素。对于子数组 $$$[3, 3]$$$,最佳总和仍然是 $$$4$$$。
- 对于 $$$k = 3$$$,您必须增加所有元素。对于子数组 $$$[1, 3]$$$,最佳总和变为 $$$(-2 + 5) + (-7 + 5) + (-1 + 5) = 5$$$。