P14458 [ICPC 2025 Xi'an R] Let's Make a Convex!

Kevin 是 **国际凸多边形锦标赛（International Convex Polygon Championship, ICPC）** 的首席评委。他为比赛提出了一道几何题。然而，由于他在几何方面经验不足，未能生成正确的凸多边形样例。 为了证明自己的几何能力，Kevin 开始玩起了木棍。他有 $n$ 根木棍，第 $i$ 根木棍的长度为 $a_i$。他希望从中选出 $k$ 根木棍，使它们能够组成一个非退化的凸多边形。 由于需要更强的测试数据，Kevin 想让所形成的多边形的周长最大化（即最大化所选木棍长度之和 $\sum a_i$）。请你帮他计算出对于每一个整数 $k$（$1 \le k \le n$），所能得到的最大周长。如果无法组成多边形，则输出单个整数 $0$。

输入包含多组测试数据。 第一行包含一个整数 $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$。

对于每个测试用例，输出一行，包含 $n$ 个整数，分别表示当选择 $k = 1, 2, \ldots, n$ 根木棍时能得到的最大周长。 如果无法组成凸多边形，则输出单个整数 $0$。

在第一个测试用例中，可以证明无法用 $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 完成