Rikka with Subset

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

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

Description

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?

Input

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).

Output

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.

Sample Input

2 3 1 1 1 5 1 2 3 4 5

Sample Output

7 11 12 129 201 231 239 240

Hint

wange2014

Source

2016 Multi-University Training Contest 8

提交代码