405668: GYM102028 I Distance

There are $$$n$$$ points on a horizontal line, labelled with $$$1$$$ through $$$n$$$ from left to right.

The distance between the $$$i$$$-th point and the $$$(i + 1)$$$-th point is $$$a_i$$$.

For each integer $$$k$$$ ranged from $$$1$$$ to $$$n$$$, you are asked to select exactly $$$k$$$ different given points on the line to maximize the sum of distances between all pairs of selected points.

The input contains several test cases, and the first line contains a positive integer $$$T$$$ indicating the number of test cases which is up to $$$1000$$$.

For each test case, the first line contains an integer $$$n$$$ indicating the number of points, where $$$2 \leq n \leq 10^5$$$.

The second line contains $$$(n - 1)$$$ positive integers $$$a_1, a_2, \cdots, a_{n - 1}$$$, where $$$1 \leq a_i \leq 10^4$$$.

We guarantee that the sum of $$$n$$$ in all test cases is up to $$$10^6$$$.

For each test case, output a line containing $$$n$$$ integers, the $$$i$$$-th of which is the maximum sum of distances in case $$$k = i$$$. You should output exactly one whitespace between every two adjacent numbers and avoid any trailing whitespace in this line.

1
5
2 3 1 4

0 10 20 34 48

The figure below describes the sample test case.

The only best selection for $$$k = 2$$$ should choose the leftmost and the rightmost points, while a possible best selection for $$$k = 3$$$ could contain any extra point in the middle.