题目描述

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

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

1. 选择数组 $a$ 中的任意一个元素并将其移动到数组的最右端（可以选择最后一个元素，此时数组不会改变）；
2. 输出数组 $a$ 最后 $k$ 个元素的和；
3. 将第一步选择的元素移回其原始位置（恢复原始数组 $a$）。

对于每个 $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$ 时能够输出的最大值。

说明/提示

以题目描述中的第一个测试用例为例：

• 当 $k=1$ 时，可以选择将第 $6$ 个元素移动到末尾，数组变为 $[13, 5, 10, 14, 8, 13, 15]$，输出值为 $15$；
• 当 $k=2$ 时，可以选择将第 $6$ 个元素移动到末尾，数组变为 $[13, 5, 10, 14, 8, 13, 15]$，输出值为 $13 + 15 = 28$；
• 当 $k=3$ 时，可以选择将第 $4$ 个元素移动到末尾，数组变为 $[13, 5, 10, 8, 15, 13, 14]$，输出值为 $15 + 13 + 14 = 42$；
• 当 $k=4$ 时，可以选择将第 $5$ 个元素移动到末尾，数组变为 $[13, 5, 10, 14, 15, 13, 8]$，输出值为 $14 + 15 + 13 + 8 = 50$；
• 当 $k=5$ 时，可以选择将第 $1$ 个元素移动到末尾，数组变为 $[5, 10, 14, 8, 15, 13, 13]$，输出值为 $14 + 8 + 15 + 13 + 13 = 63$；
• 当 $k=6$ 时，可以选择将第 $1$ 个元素移动到末尾，数组变为 $[5, 10, 14, 8, 15, 13, 13]$，输出值为 $10 + 14 + 8 + 15 + 13 + 13 = 73$；
• 当 $k=7$ 时，可以选择将第 $6$ 个元素移动到末尾，数组变为 $[13, 5, 10, 14, 8, 13, 15]$，输出值为 $13 + 5 + 10 + 14 + 8 + 13 + 15 = 78$。

翻译由 DeepSeek V3 完成

样例

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