题目描述

给定一个序列 {$a_n$} 与整数 $x$

定义 $f(k)$ 表示经过如下操作后,序列 $a$ 中最大的连续子段和: 将 $a$ 中 $k$ 个不同的位置上的数加上 $x$，请求出：

$f(k)$， $k \in [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,...,a_n$ ( $-10^5\le a_i \le 10^5$ )

所有数据的 $n$ 的总和不超过 $5000$

输出格式

对于每组测试数据，输出一行，共 $n+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

10 12 14 16 18
0 4 4 5
4 6 6 7 7 7 7 8 8 8 8