Demonic Subset

Limits 2.5s, 512 MB

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

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 KK will be too easy, you need to find the answer for all possible KK (1 to NN).

Input

The first line contains an integer, TT (1T101 ≤ T ≤ 10), number of tests. The second line contains an integer, NN (1N1051 ≤ N ≤ 10^5), number of elements in AA. Next line contains NN characters denoting the elements of the array AA (1A[i]1091 ≤ A[i] ≤ 10^9).

Output

For each test case print a line contains exactly NN numbers denoting the answer for all possible KK (1 to NN). 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