Kevin と Nivek は「The Best Kevin」の称号をかけて競い合っている。彼らは $n$ 回の試合を通して勝者を決定することにした。
各試合は以下の 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$) が与えられる。
次の行には、$n$ 個の整数 $a_1, a_2, \dots, a_n$ ($-1 \le a_i \le 10^9$) が与えられる。
$a_i = -1$ の場合、その試合はタイプ 2 である。それ以外の場合、その試合はタイプ 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$ の時間を費やすと、すべての試合に勝つことができる。