Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Demonic Subset

By IamHot · 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

Discussion

Statistics


76% Solution Ratio

SwampFireEarliest, Sep '19

imAnikFastest, 0.5s

RezwanArefin01Lightest, 14 MB

kzvd4729Shortest, 2200B

Submit

Login to submit