import sys
def input():
return sys.stdin.readline().rstrip("\r\n")
def maps():
return [int(i) for i in input().split()]
for _ in range(int(input())):
n, x = maps()
a = maps()
ok, cur_sum, max_sum = True, 0, 0
end_idx = n - 1
for i in range(n):
if a[i] < 0:
ok = False
cur_sum += a[i]
if cur_sum > max_sum:
max_sum = cur_sum
end_idx = i
elif cur_sum < 0:
cur_sum = 0
if ok:
print(*[max_sum + i * x for i in range(n + 1)])
else:
lzy = [-float("inf")] * (n + 1)
for i in range(n):
cur_sum = 0
for j in range(i, n):
cur_sum += a[j]
lzy[j - i + 1] = max(lzy[j - i + 1], cur_sum)
res = []
for k in range(n + 1):
bst = 0
for i in range(n + 1):
bst = max(
bst, lzy[i] + min(i, k) * x
) res.append(bst)
print(" ".join(map(str, res)))
#include <bits/stdc++.h>
using namespace std;
template<typename T> using vt = vector<T>;
using ll = long long;
using ld = long double;
using vi = vt<int>;
using ii = pair<int, int>;
using vii = vt<ii>;
template<typename T> using mipq = priority_queue<T, vt<T>,
greater<T>>;
template<typename T> using mapq = priority_queue<T>;
#define sqr(x) ((x)*(x))
#define debug(x) cerr << #x << " -> " << (x) << '\n'
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define sz(x) (int) (x).size()
#define F first
#define S second
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
const int inf = 1e9 + 7;
const ll infll = 1e18 + 3;
ll fgcd(ll a, ll b) {while(b) swap(b, a %= b); return a;}
ll fpow(ll a, ll b, const ll c) {
ll ans = 1; a %= c;
for(; b; b >>= 1, a = a * a % c) if(b & 1) ans = ans * a % c;
return ans;
}
ll fpow(ll a, ll b) {
ll ans = 1;
for(; b; b >>= 1, a *= a) if(b & 1) ans *= a;
return ans;
}
int flog(int x) {return 31 - __builtin_clz(x);}
int flog(ll x) {return 63 - __builtin_clzll(x);}
void setIO(string name = "") {
cin.tie(0)->sync_with_stdio(0);
if (fopen((name+".in").c_str(), "r")) {
freopen((name+".in").c_str(), "r", stdin);
freopen((name+".out").c_str(), "w", stdout);
}
}
const int N = 5e3 + 10;
int a[N], dp[N];
int n, t, x;
signed main() {
setIO("");
// freopen("milkvisits.in", "r", stdin);
// freopen("milkvisits.out", "w", stdout);
cin >> t;
while (t--) {
cin >> n >> x;
for (int i = 1; i <= n; i++) cin >> a[i], dp[i] = -inf;
for (int i = 1; i <= n; i++) {
int sum = 0;
for (int j = i; j <= n; j++) {
sum += a[j];
dp[j - i + 1] = max(dp[j - i + 1], sum);
}
}
for (int k = 0; k <= n; k++) {
int mx = 0;
for (int i = 1; i <= n; i++) {
mx = max(mx, dp[i] + x * min(i, k));
}
cout << mx << " \n"[k == n];
}
}
}
1612A - Distance | 520A - Pangram |
124A - The number of positions | 1041A - Heist |
901A - Hashing Trees | 1283A - Minutes Before the New Year |
1654D - Potion Brewing Class | 1107B - Digital root |
25A - IQ test | 785A - Anton and Polyhedrons |
1542B - Plus and Multiply | 306A - Candies |
1651C - Fault-tolerant Network | 870A - Search for Pretty Integers |
1174A - Ehab Fails to Be Thanos | 1169A - Circle Metro |
780C - Andryusha and Colored Balloons | 1153A - Serval and Bus |
1487C - Minimum Ties | 1136A - Nastya Is Reading a Book |
1353B - Two Arrays And Swaps | 1490E - Accidental Victory |
1335A - Candies and Two Sisters | 96B - Lucky Numbers (easy) |
1151B - Dima and a Bad XOR | 1435B - A New Technique |
1633A - Div 7 | 268A - Games |
1062B - Math | 1294C - Product of Three Numbers |