Problem Description

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.

Input Format

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

Output Format

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

Hint

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.