题目描述

Kevin is the chief judge of the $\textit{International Convex Polygon Championship (ICPC)}$. He proposed a geometry task for the contest. However, due to his lack of experience in geometry, he was unable to generate the correct convex polygons for the task.

To prove his geometry skills, Kevin starts playing with sticks. He has $n$ sticks, the $i$-th of which has a length $a_i$. He would like to select $k$ sticks so that they can be arranged as a non-degenerate convex polygon.

Since stronger test data are needed, Kevin wants to maximize the perimeter of the polygon (i.e., maximize the sum of $a_i$ of all sticks in the subset). Could you help him find out the value for all integers $k$ from $1$ to $n$? If no such polygon exists, tell him a single integer $0$ instead.

输入格式

The input consists of multiple test cases. The first line contains an integer $t$ ($1 \leq t \leq 10^5$), the number of test cases. For each test case:

• The first line contains a single integer $n$ ($1 \leq n \leq 2 \cdot 10^5$), which is the number of sticks.
• The second line contains $n$ integers $a_1, \ldots, a_n$ ($1 \leq a_i \leq 10^9$), which are the lengths of each stick.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

输出格式

For each test case, output a single line containing $n$ integers, representing the maximal perimeter of the polygon. Specifically, if no such polygon exists, output a single integer $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

提示

In the first test case, it can be shown that there does not exist a convex polygon of $1$ or $2$ sides. When $k = 3$, the maximal perimeter of the convex polygon is $12$, since sticks of side lengths $3$, $4$, and $5$ are known for forming a right triangle. Similarly, when $k = 4$, the maximal perimeter of the polygon is $2 + 3 + 4 + 5 = 14$; when $k = 5$, selecting all sticks is a valid scheme and obtains a perimeter of $1 + 2 + 3 + 4 + 5 = 15$.

In the second test case, it can be proven that no matter how the sticks are selected, they cannot form a convex polygon.