宝藏拾取

题号：NC302222
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

$\hspace{15pt}$ 给定一个长度为 $n$ 的宝藏数组 $a_1,a_2,\dots,a_n$ 。Bingbong 从起点 $s$ 出发，向索引增大的方向移动。对于经过的每个位置 $i$ ：
$\hspace{23pt}\bullet\,$ 若是起点 $i=s$ ，则直接获得 $a_i$ ；
$\hspace{23pt}\bullet\,$ 若 $i>s$ ，当且仅当当前持有的宝藏总和 $sum \ge a_i$ 时，可以获得 $a_i$ ；
$\hspace{23pt}\bullet\,$ 每个位置的宝藏只能在其被经过时领取一次，且移动过程不可逆。
$\hspace{15pt}$ 现在你需要对于任意的 $1\leq s\leq n$ ，回答以 $s$ 为起点可以获得的最多宝藏数量，每次回答相互独立，互不影响。

输入描述:

每个测试文件均包含多组测试数据。第一行输入一个整数 ，代表数据组数，每组测试数据描述如下：

第一行输入一个整数 ，表示宝藏数组长度。
第二行输入  个整数 ，表示每个位置的宝藏数量。

除此之外，保证单个测试文件的  之和不超过 。

输出描述:

对于每一组测试数据，新起一行输出  个整数，分别表示以  为起点可获得的最大宝藏数量。

示例1

输入

复制

4
1
1
4
2 4 1 3
5
1 2 5 4 3
6
6 5 4 3 2 1

输出

复制

1
6 8 1 3
1 2 12 7 3
21 15 10 6 3 1

说明

对于第二组测试数据：
当  时，移动路线为 ，获得  个宝藏。
当  时，移动路线为 ，获得  个宝藏。
当  时，移动路线为 ，获得  个宝藏。
当  时，移动路线为 ，获得  个宝藏。