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
| Input | Output |
|---|---|
3 3 1 1 1 3 1 2 3 4 1 2 3 4 | 7 11 12 11 21 24 26 58 76 80 |
