题目描述

给定一个由 $n$ 个整数组成的数组 $a$ 。

对于每一个从 $1$ 到 $n$ 的整数 $k$ ，你需要执行以下操作：

1 从数组 $a$ 中任选一个元素，将它移动到数组的末尾（你也可以选择最后一个元素，此时数组不会改变）；

2 输出数组 $a$ 的后 $k$ 个元素之和；

3 将第一步移动的元素还原到原来的位置（恢复原始数组 $a$ ）。

对于每个 $k$ ，你应选择一个最优的移动方式，使得输出的后 $k$ 项的和尽可能大。

请你计算并输出每个 $k$ 的最大可能值。

输入格式

第一行包含一个整数 $t$ （ $1 \le t \le 10^4$ ），表示测试用例的个数。

接下来的每组测试用例包括两行：

第一行一个整数 $n$ （ $1 \le n \le 2 \cdot 10^5$ ）；

第二行 $n$ 个整数 $a_1, a_2, \dots, a_n$ （ $1 \le a_i \le 10^9$ ）。

额外保证：所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$ 。

对于每个测试用例，输出 $n$ 个整数，第 $i$ 个整数表示当 $k=i$ 时你所能获得的最大和。

4
7
13 5 10 14 8 15 13
6
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
1
42
2
7 5

15 28 42 50 63 73 78
1000000000 2000000000 3000000000 4000000000 5000000000 6000000000
42
7 12

以第一个测试用例为例：

当 $k=1$ ，将第 6 个元素（值为 15）移到末尾，数组变为 [13, 5, 10, 14, 8, 13, 15]，输出末尾元素之和：15；

当 $k=2$ ，同样移动第 6 个元素，数组为 [13, 5, 10, 14, 8, 13, 15]，输出后两项：13 + 15 = 28；

当 $k=3$ ，将第 4 个元素（值为 14）移到末尾，变为 [13, 5, 10, 8, 15, 13, 14]，后 3 项之和为 15 + 13 + 14 = 42；

以此类推。