Three Investigators

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

First, Chitanda selects a parameter $k$ and removes $a_{k+1}, a_{k+2}, \ldots, a_n$. Then exactly $k$ integers remain in the sequence $a$.

Next, Skywalkert can select a subsequence of $a$ and remove it from $a$. If the selected subsequence is $a_{p_1}, a_{p_2}, \ldots, a_{p_m}$, then $p_1 < p_2 < \ldots < p_m$ and $a_{p_1} \le a_{p_2} \le \ldots \le a_{p_m}$ must hold.

Skywalkert can perform this operation at most 5 times. His score is the sum of all integers he selects in these operations.

For each possible parameter $k$ that Chitanda selects, find the maximum score Skywalkert can achieve.

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

Each test case has one line with an integer $n$ ($1 \le n \le 100000$), the length of the sequence. The next line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$).

The sum of $n$ over all test cases is at most 500000.

For each test case, print one line with $n$ integers $s_1, s_2, \ldots, s_n$ separated by spaces, where $s_i$ is the maximum score Skywalkert can achieve when $k = i$.