Kevin と Nivek は「The Best Kevin」の称号をかけて競い合っている。彼らは $n$ 回の試合を通して勝者を決定することを目指している。

$i$ 番目の試合は、以下の2種類のいずれかである。

• タイプ 1: Kevin が Nivek を倒して試合に勝つためには、$a_i$ の時間を費やす必要がある。Kevin がこの試合に $a_i$ の時間を費やさなければ、Nivek が試合に勝つ。
• タイプ 2: この試合の結果は、それまでの対戦成績に依存する。この試合までの時点で Kevin の勝利数が Nivek の勝利数以上であれば、Kevin が勝つ。そうでなければ、Nivek が勝つ。

Kevin は、少なくとも $k$ 回の試合に勝つために必要な最小の時間を知りたいと考えている。$k = 0, 1, \dots, n$ のそれぞれについて答えを出力せよ。

入力

各テストケースには複数のテストケースが含まれる。最初の行にはテストケースの数 $t$ ($1 \le t \le 10^4$) が含まれる。

各テストケースの記述は以下の通りである。 各テストケースの最初の行には、試合数を示す単一の整数 $n$ ($1 \le n \le 3 \cdot 10^5$) が含まれる。 2行目には、$n$ 個の整数 $a_1, a_2, \dots, a_n$ ($-1 \le a_i \le 10^9$) が含まれる。

$a_i = -1$ の場合、$i$ 番目の試合はタイプ 2である。それ以外の場合、$i$ 番目の試合はタイプ 1であり、$a_i$ は Kevin がこの試合に勝つために費やす必要がある時間を表す。

すべてのテストケースにおける $n$ の合計は $3 \cdot 10^5$ を超えないことが保証される。

出力

各テストケースについて、$n + 1$ 個の整数を出力せよ。$i$ 番目の整数は、少なくとも $i - 1$ 回の試合に勝つために必要な最小の時間を表す。

入出力例

入力 1

3
5
-1 -1 -1 -1 -1
5
3 2 5 4 1
5
100 -1 -1 -1 1

出力 1

0 0 0 0 0 0
0 1 3 6 10 15
0 1 100 100 100 101

注記

最初のテストケースでは、すべての試合がタイプ 2 である。Kevin は自動的にすべての試合に勝つことができる。

2番目のテストケースでは、すべての試合がタイプ 1 である。Kevin は $a_i$ の昇順で試合を選択することができる。

3番目のテストケースでは：

• Kevin が試合 1 に $a_1$ の時間を費やすと、試合 1, 2, 3, 4 に勝つことができる。
• Kevin が試合 5 に $a_5$ の時間を費やすと、試合 5 に勝つことができる。
• Kevin が試合 1 に $a_1$ の時間、試合 5 に $a_5$ の時間を費やすと、すべての試合に勝つことができる。