Given an integer sequence $$$a_1, a_2, \cdots, a_n$$$ of length $$$n$$$, divide the sequence into $$$k$$$ continuous non-empty subarrays such that each element belongs to exactly one subarray. Let $$$s_i$$$ be the sum of elements in the $$$i$$$-th subarray from left to right, for each $$$1 \le k \le n$$$, calculate the maximum value of $$$$$$\sum\limits_{i = 1}^k i \times s_i$$$$$$
More formally, for each $$$1 \le k \le n$$$, let $$$r_0 = 0$$$ and $$$r_k = n$$$, you need to find $$$(k - 1)$$$ integers $$$r_1, r_2, \cdots, r_{k - 1}$$$ such that $$$r_0 \lt r_1 \lt r_2 \lt \cdots \lt r_{k - 1} \lt r_k$$$ and maximize $$$$$$\sum\limits_{i = 1}^k i \times (\sum\limits_{j = r_{i - 1} + 1}^{r_i} a_j)$$$$$$
There are multiple test cases. The first line of the input contains an integer $$$T$$$ indicating the number of test cases. For each test case:
The first line contains one integer $$$n$$$ ($$$1 \le n \le 5 \times 10^5$$$) indicating the length of the sequence.
The second line contains $$$n$$$ integers $$$a_1, a_2, \cdots, a_n$$$ ($$$-10^6 \le a_i \le 10^6$$$) indicating the sequence.
It's guaranteed that the sum of $$$n$$$ of all test cases will not exceed $$$5 \times 10^5$$$.
For each test case, output one line containing $$$n$$$ integers $$$v_1, v_2, \cdots, v_n$$$ separated by a space, where $$$v_i$$$ is the answer for $$$k = i$$$.
261 3 -4 5 -1 -21100
2 4 5 3 1 -2 100
For the first sample test case, consider $$$k = 3$$$, we can divide the sequence into $$$\{\{1\}, \{3, -4\}, \{5, -1, -2\}\}$$$. The answer is $$$1 \times 1 + 2 \times (3 - 4) + 3 \times (5 - 1 - 2) = 5$$$.
