18594번 - Three Investigators 다국어

문제

Chitanda owns a sequence a₁, a₂, . . . , 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, . . . , 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_p1, a_p2, . . . , a_pm. He should ensure that p₁ < p₂ < . . . < p_m and a_p1 ≤ a_p2 ≤ . . . ≤ a_pm.

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.

For each possible parameter k selected by Chitanda, write a program to help Skywalkert know the maximum score he can achieve.

입력

The first line of the input contains an integer T (1 ≤ T ≤ 10 000), denoting the number of test cases.

In each test case, there is one integer n (1 ≤ n ≤ 100 000) on the first line, denoting the length of a.

In the second line of a test case, there are n integers a₁, a₂, . . . , a_n (1 ≤ a_i ≤ 10⁹), denoting the sequence.

It is guaranteed that the sum of n in all test cases is at most 500 000.

출력

For each test case, print a single line containing n integers s₁, s₂, . . . , s_n, where si denotes the maximum score of Skywalkert when k = i.

제한

힌트