I. Kevin and Nivek
time limit per test
4 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Kevin and Nivek are competing for the title of "The Best Kevin". They aim to determine the winner through $$$n$$$ matches.

The $$$i$$$-th match can be one of two types:

  • Type 1: Kevin needs to spend $$$a_i$$$ time to defeat Nivek and win the match. If Kevin doesn't spend $$$a_i$$$ time on it, Nivek will win the match.
  • Type 2: The outcome of this match depends on their historical records. If Kevin's number of wins is greater than or equal to Nivek's up to this match, then Kevin wins. Otherwise, Nivek wins.

Kevin wants to know the minimum amount of time he needs to spend to ensure he wins at least $$$k$$$ matches.

Output the answers for $$$k = 0, 1, \ldots, n$$$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$) — the number of matches.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$-1 \leq a_i \leq 10^9$$$).

If $$$a_i = -1$$$, the $$$i$$$-th match is of Type 2. Otherwise, the $$$i$$$-th match is of Type 1, and $$$a_i$$$ represents the amount of time Kevin needs to spend to win this match.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$3 \cdot 10^5$$$.

Output

For each test case, output $$$n + 1$$$ integers. The $$$i$$$-th integer represents the minimum amount of time to win at least $$$i-1$$$ matches.

Example
Input
3
5
-1 -1 -1 -1 -1
5
3 2 5 4 1
5
100 -1 -1 -1 1
Output
0 0 0 0 0 0 
0 1 3 6 10 15 
0 1 100 100 100 101
Note

In the first test case, all matches are of Type 2. Kevin can automatically win all matches.

In the second test case, all matches are of Type 1. Kevin can choose matches in increasing order of $$$a_i$$$.

In the third test case:

  • If Kevin spends $$$a_1$$$ time on match $$$1$$$, he can win matches $$$1, 2, 3, 4$$$.
  • If Kevin spends $$$a_5$$$ time on match $$$5$$$, he can win match $$$5$$$.
  • If Kevin spends $$$a_1$$$ time on match $$$1$$$ and $$$a_5$$$ time on match $$$5$$$, he can win all matches.