U552155 J-C 序列分段

给定长度为 $n$ 的序列 $a$，要求将 $a$ 分割成恰好 $k$ 段，每一段内的所有数字都求和，得到一个长度为 $k$ 的序列 $b$。 接着，最大化以下式子的和： $$ \sum\limits_{i=1}^k i\times b_i。 $$ 即：$b_1\times1+b_2\times 2+b_3 \times3+...+b_k\times k$。 更通俗的： 请最大化：“第一段的和乘 $1$，加上第二段的和乘 $2$，一直加到第 $k$ 段的和乘 $k$ ”。 现在，请你对每一个 $k\ (1 \leq k \leq n)$，都求出并回答上述式子的最大值吧。

**本题有多组测试数据。** 输入的第一行包含一个正整数 $T$，表示数据组数。 接下来包含 $T$ 组数据，每组数据的格式如下： 第一行一个正整数 $n$，表示序列 $a$ 的长度。 第二行 $n$ 个整数 $a_1, a_2, \cdots,a_n$，表示序列 $a$。

对于每组测试数据： 在单独的一行输出由空格分隔的 $n$ 个整数，其中第 $i$ 个整数表示：把数组分为 $i$ 段时，上述式子的最大值。

**【样例 1 解释】** 对于第一组测试数据，我们考虑 $k=3$ 的情况，可以把序列分为： $\{\{1\},\{3, -4\}, \{5, -1, -2\} \}$。 此时 $b=\{1, 3+(-4), (5+(-1)+(-2))\}=\{1,-1,2\}$。 而题目所求式子的值为：$1\times1+(-1)\times 2+2 \times3=5$。 因此第一组测试数据中，第三个数字的值是 $5$。 （可以证明，不存在比 $5$ 更优的答案。） **【数据范围】** 令 $N$ 表示 $T$ 组数据中 $n$ 的总和。 对于 $\rm 30\%$ 的数据有：$T = 1, 1 \leq N \leq 15$。 对于 $60\%$ 的数据有：$1 \leq T \leq 10, 1 \leq N \leq 200$。 对于所有的测试数据有： $1 \leq T \leq 100, 1 \leq N \leq 2 \times 10^5\ ,-10^6 \leq a_i \leq 10^6$。