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

Submit

Login to submit.

Statistics

80% Solution Ratio
SwampFireEarliest, Sep '19
mumith_fahim99Fastest, 0.3s
mumith_fahim99Lightest, 9.3 MB
Deshi_TouristShortest, 2199B
Toph uses cookies. By continuing you agree to our Cookie Policy.