Description

Kevin 是 国际凸多边形锦标赛（International Convex Polygon Championship, ICPC） 的首席评委。他为比赛提出了一道几何题。然而，由于他在几何方面经验不足，未能生成正确的凸多边形样例。

为了证明自己的几何能力，Kevin 开始玩起了木棍。他有 $n$ 根木棍，第 $i$ 根木棍的长度为 $a_i$。他希望从中选出 $k$ 根木棍，使它们能够组成一个非退化的凸多边形。

由于需要更强的测试数据，Kevin 想让所形成的多边形的周长最大化（即最大化所选木棍长度之和 $\sum a_i$）。请你帮他计算出对于每一个整数 $k$（$1 \le k \le n$），所能得到的最大周长。如果无法组成多边形，则输出单个整数 $0$。

Input Format

输入包含多组测试数据。

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

对于每个测试用例：

• 第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$），表示木棍的数量；
• 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 10^9$），表示每根木棍的长度。

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

Output Format

对于每个测试用例，输出一行，包含 $n$ 个整数，分别表示当选择 $k = 1, 2, \ldots, n$ 根木棍时能得到的最大周长。

如果无法组成凸多边形，则输出单个整数 $0$。

7
5
1 2 3 4 5
5
1 2 4 8 16
5
2 2 2 2 2
4
1 4 10 7
2
1 2
3
2 3 4
4
3 1 2 6

0 0 12 14 15
0 0 0 0 0
0 0 6 8 10
0 0 21 22
0 0
0 0 9
0 0 0 0

Hint

在第一个测试用例中，可以证明无法用 $1$ 根或 $2$ 根木棍组成凸多边形。

当 $k = 3$ 时，最大周长为 $12$，因为长度为 $3$、$4$ 和 $5$ 的三根木棍可以组成一个直角三角形。
当 $k = 4$ 时，最大周长为 $2 + 3 + 4 + 5 = 14$。
当 $k = 5$ 时，选择所有木棍是有效的方案，此时周长为 $1 + 2 + 3 + 4 + 5 = 15$。

在第二个测试用例中，可以证明无论如何选择木棍，都无法组成凸多边形。

翻译由 ChatGPT-5 完成