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.