Rikka with Subset

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?

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, print a line contains exactly n numbers, the ith number is the value of the array when K=i. The answer may be very large, so you only need to print the answer module 998244353.

2
3
1 1 1
5
1 2 3 4 5

7 11 12
129 201 231 239 240

学军中学

2016 Multi-University Training Contest 8