题目描述

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.

:::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.