P17474 [ICPC 2018 Jiaozuo R] 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.

The figure below describes the sample test case. :::align{center}  ::: 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.