题目描述

给定长度为 $n$ 的整数序列 $a_1, a_2, \cdots, a_n$，请将序列分成 $k$ 段连续且非空的子数组，使得序列中的每个元素恰属于一个子数组。令 $s_i$ 表示从左到右第 $i$ 个子数组里的元素之和，对于每个 $1 \le k \le n$，求下式的最大值。

$$\sum\limits_{i = 1}^k i \times s_i$$

更正式地，对于每个 $1 \le k \le n$，令 $r_0 = 0$ 以及 $r_k = n$，您需要找到 $(k - 1)$ 个整数 $r_1, r_2, \cdots, r_{k - 1}$ 满足 $r_0 < r_1 < r_2 < \cdots < r_{k - 1} < r_k$，并最大化下式的值。

$$\sum\limits_{i = 1}^k i \times (\sum\limits_{j = r_{i - 1} + 1}^{r_i} a_j) $$

输入格式

有多组测试数据。第一行输入一个整数 $T$ 表示测试数据组数，对于每组测试数据：

第一行输入一个整数 $n$（$1 \le n \le 5 \times 10^5$）表示序列的长度。

第二行输入 $n$ 个整数 $a_1, a_2, \cdots, a_n$（$-10^6 \le a_i \le 10^6$）表示序列。

保证所有数据 $n$ 之和不超过 $5 \times 10^5$。

输出格式

每组数据输出一行 $n$ 个由单个空格分隔的整数 $v_1, v_2, \cdots, v_n$，其中 $v_i$ 表示 $k = i$ 时的答案。

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

2 4 5 3 1 -2
100

提示

对于第一组样例数据，考虑 $k = 3$，可以将序列分割为 $\{\{1\}, \{3, -4\}, \{5, -1, -2\}\}$。答案是 $1 \times 1 + 2 \times (3 - 4) + 3 \times (5 - 1 - 2) = 5$。