Read problems statements in [Hindi], [Mandarin Chinese], [Russian], [Vietnamese], and [Bengali] as well.

Chef has a machine which he uses to rotate sequences. If he puts a sequence $S_{1}, S_{2}, \ldots, S_{N}$ into the machine, it produces the sequence $S_{2}, S_{3}, \ldots, S_{N}, S_{1}$, i.e. the first element of the sequence is moved to the end.

Chef is definitely not a newbie ― he knows about trivial things like finding the maximum sum of a contiguous subsequence. Therefore, he now made a difficult problem to challenge himself:

You are given a sequence $A_{1}, A_{2}, \ldots, A_{N}$. For each $k$ ($0 ≤ k ≤ N-1$), consider the sequence produced by inserting it into the machine repeatedly $k$ times (i.e. inserting $A$ into the machine and replacing $A$ by the sequence it produces, $k$ times); find the maximum sum of a non empty contiguous subsequence of this sequence.

However, to solve this problem, Chef needs the help of a pro. Solve it for him.

------ Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains a single integer $N$.
The second line contains $N$ space-separated integers $A_{1}, A_{2}, \ldots, A_{N}$.

------ Output ------
For each test case, print a single line containing $N$ space-separated integers. For each valid $i$, the $i$-th of these integers should denote the largest sum of a non empty contiguous subsequence of the sequence produced by the machine after $i-1$ repeated insertions.

------ Constraints ------
$1 ≤ T ≤ 100$
$1 ≤ N ≤ 5 \cdot 10^{5}$
$|A_{i}| ≤ 10^{9}$ for each valid $i$
the sum of $N$ over all test cases does not exceed $5 \cdot 10^{5}$

----- Sample Input 1 ------
1

4

-5 4 1 2
----- Sample Output 1 ------
7 7 4 5
----- explanation 1 ------
Example case 1:
- After zero insertions, $A = [-5, 4, 1, 2]$. The contiguous subsequence with the maximum sum is $A = [4, 1, 2]$.
- After one insertion, $A = [4, 1, 2, -5]$. The contiguous subsequence with the maximum sum is $A = [4, 1, 2]$.
- After two insertions, $A = [1, 2, -5, 4]$. The contiguous subsequence with the maximum sum is $A = [4]$.
- After three insertions, $A = [2, -5, 4, 1]$. The contiguous subsequence with the maximum sum is $A = [4, 1]$.

见题面

见题面