题目描述
Arnabjan, The Picnic man of CSE batch 2013-17 organises a picnic for the
whole batch.During Picnic ,he found n numbers.As the batch has scarcity of
money,they decided to eat subsequence of array.A subsequence can be
eaten if they are continous. Subsequence is poisonous if their sum is greater
than K. So they want to know number of possible subsequence of length i
which are fit for eating.As we know the whole batch is weak in mathematics.
So, please help Arnabjan.
Input : First line of the input contains number of test cases T. Each test case has two lines.
First line has N, the number of elements of the array ,
K ,Threshold sum of subsequence (If sum is greater than k,the subsequence is poisonous)
followed by the second line, the elements of the array.
Output : Output n numbers separated by space, where each number denotes numbers of possible subsequence of length i, [1 ≤ i ≤ n].
1 ≤ T ≤ 20
1<N<1000000
1 ≤ K ≤ 1000000000000
1 ≤ array element ≤ 100000000
SAMPLE INPUT
2
3 4
1 2 3
4 12
2 1 3 4
SAMPLE OUTPUT
3 1 0
4 3 2 1
Explanation
For Case 1 :
N=3 K=4
so safe subsequences are :
Length 1 : [{1},{2},{3}] = 3
Length 2 : [{1,2}]=1
Length 3 :[]=0
For Case 2 :
N=4 K=12
Length 1 : [{2},{1},{3},{4}] = 4
Length 2 : [{2,1},{1,3},{3,4}]=3
Length 3 :[{2,1,3},{1,3,4}]=2
Length 3 :[{2,1,3,4}]=1
输入格式
见题面
输出格式
见题面