#214598. [ICPC 2025 Xi'an R] Let's Make a Convex!

Kevin is the chief judge of the . 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 sticks, the -th of which has a length . He would like to select 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 of all sticks in the subset). Could you help him find out the value for all integers from to ? If no such polygon exists, tell him a single integer instead.

The input consists of multiple test cases. The first line contains an integer (), the number of test cases. For each test case:

• The first line contains a single integer (), which is the number of sticks.
• The second line contains integers (), which are the lengths of each stick.

It is guaranteed that the sum of over all test cases does not exceed .

For each test case, output a single line containing integers, representing the maximal perimeter of the polygon. Specifically, if no such polygon exists, output a single integer .

样例输入 1

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

样例输出 1

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 or sides. When , the maximal perimeter of the convex polygon is , since sticks of side lengths , , and are known for forming a right triangle. Similarly, when , the maximal perimeter of the polygon is ; when , selecting all sticks is a valid scheme and obtains a perimeter of .

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