# Increase Subarray Sums solution codeforces

You are given an array a1,a2,,ana1,a2,…,an, consisting of nn integers. You are also given an integer value xx.

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

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

Calculate f(k)f(k) for all kk from 00 to nn.

Input

The first line contains a single integer tt (1t50001≤t≤5000) — the number of testcases.

The first line of the testcase contains two integers nn and xx (1n50001≤n≤50000x1050≤x≤105) — the number of elements in the array and the value to add.

# Increase Subarray Sums solution codeforces

The second line contains nn integers a1,a2,,ana1,a2,…,an (105ai105−105≤ai≤105).

The sum of nn over all testcases doesn’t exceed 50005000.

Output

For each testcase, print n+1n+1 integers — the values of f(k)f(k) for all kk from 00 to nn.

Example

input

# Increase Subarray Sums solution codeforces

Copy
3
4 2
4 1 3 2
3 5
-2 -7 -1
10 2
-6 -1 -2 4 -6 -1 -4 4 -5 -4


output

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

Note

# Increase Subarray Sums solution codeforces

In the first testcase, it doesn’t matter which elements you add xx to. The subarray with the maximum sum will always be the entire array. If you increase kk elements by xxkxk⋅x will be added to the sum.

In the second testcase:

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