Problem Description

Chitanda owns a sequence $a_1,a_2,\dots,a_n$ with $n$ integers, and she wants to play a game with Skywalkert.

First, Chitanda will select a parameter $k$ and remove $a_{k+1},a_{k+2},\dots,a_n$. Thus there will be exactly $k$ integers in sequence $a$.

Then Skywalkert can select a subsequence of $a$ and remove it from $a$. Assume the selected subsequence is $a_{p_1},a_{p_2},\dots,a_{p_m}$, he should ensure $p_1<p_2<\dots<p_m$ and $a_{p_1}\leq a_{p_2}\leq\dots\leq a_{p_m}$.

Skywalkert can do the above operation for no more than $5$ times. His score is the sum of all the integers selected by him in these no more than $5$ operations.

Given the parameter $k$ selected by Chitanda, write a program to help Skywalkert maximize his score.

Input

The first line of the input contains an integer $T(1\leq T\leq 10000)$, denoting the number of test cases.

In each test case, there is one integer $n(1\leq n\leq 100000)$ in the first line, denoting the length of $a$.

In the second line, there are $n$ integers $a_1,a_2,...,a_n(1\leq a_i\leq 10^9)$, denoting the sequence.

It is guaranteed that $\sum n\leq 500000$.

Output

For each test case, print a single line containing $n$ integers $s_1,s_2,\dots,s_n$ , where $s_i$ denotes the maximum score of Skywalkert when $k=i$.

1
8
8 7 6 5 1 3 2 4

8 15 21 26 27 30 30 34