# Demonic Subset IamHot Practice Contest for the...
Limits 8s, 512 MB

Lets not waste your time with long tiring problem statement and just go straight to the point. You are given an array A containing N numbers. You are also given a function. You need to find the result of the function using array A for a specific K.

function solveMeIfYouCan(A,K)
result = 0

subsetList = all the non empty subsets of array A

For all subset s  in subsetList
sortedSubset = sort the elements inside subset from small to large

size = element count in sortedSubset
len = min(size, K)

For i = 1 to len
result = result + sortedSubset[i]
end For

end For

return result
end function

Note: Array indexing starts from 1.


Since finding the answer for a single K will be too easy, you need to find the answer for all possible K (1 to N).

## Input

The first line contains an integer, T (1 ≤ T ≤ 10), number of tests. The second line contains an integer, N (1 ≤ N ≤ 105), number of elements in A. Next line contains N characters denoting the elements of the array A (1 ≤ A[i] ≤ 109).

## Output

For each test case print a line contains exactly N numbers denoting the answer for all possible K (1 to N). The answer may be very large, so you need to print the answer modulo 786433.

## Sample

InputOutput
3
3
1 1 1
3
1 2 3
4
1 2 3 4
7 11 12
11 21 24
26 58 76 80 DP, FFT, Math, NTT uDebug

### Submit 