Time Limit: 6000/3000 MS (Java/Others)

Memory Limit: 65536/65536 K (Java/Others)

As we know, Rikka is poor at math. Yuta is worrying about this situation, so he gives Rikka some math tasks to practice. There is one of them:

Yuta has n numbers A[1]~A[n] and a number K. For any none empty subset S of the numbers, the value of S is equal to the sum of the largest min(|S|,k) numbers in S. The value of the array A is equal to the sum of the value of all none empty subset of the numbers.

Now Yuta shows the n numbers, And he wants to know the value of the array for each K in [1,n].

It is too difficult for Rikka. Can you help her?

Yuta has n numbers A[1]~A[n] and a number K. For any none empty subset S of the numbers, the value of S is equal to the sum of the largest min(|S|,k) numbers in S. The value of the array A is equal to the sum of the value of all none empty subset of the numbers.

Now Yuta shows the n numbers, And he wants to know the value of the array for each K in [1,n].

It is too difficult for Rikka. Can you help her?

The first line contains a number t(1<=t<=10), the number of the testcases.

For each testcase, the first line contains a number n(1<=n<=100000), the number of numbers Yuta has. The second line contains n number A[1]~A[n](0<=A[i]<=10^9).

For each testcase, the first line contains a number n(1<=n<=100000), the number of numbers Yuta has. The second line contains n number A[1]~A[n](0<=A[i]<=10^9).

提交代码