Increase Subarray Sums solution codeforces

 You get an array a1,a2,…,ana1,a2,…,an, consisting of nn integers. You also get an integer 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 at exactly kk different positions. An empty subarray should also be considered, it has sum 00.Calculate f(k)f(k) for all kk from 00 to nn.

Input

The first line contains one integer  tt (1≤t≤50001≤t≤5000) – the number of test cases.

The first line of the test case contains two integers nn and xx (1≤n≤50001≤n≤5000; 0≤x≤1050≤x≤105) — the number of elements in the array and the value to add.

The second line contains nn integers a1,a2,…,ana1,a2,…,an (−105≤ai≤105−105≤ai≤105).The sum of nn over all test cases does not exceed 50005000.

Exit:

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

Example

input

To 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

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

Remark

In the first test case it doesn’t matter to which elements you add xx. The subarray with the maximum sum is always the entire array. If you increase kk elements by xx, k⋅xk⋅x is added to the sum.

In the second test case:

For  k=0k=0, the empty subarray is the best option.
For k=1k=1 it is 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 is 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 must 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].