Knapsack Count with a Missing Item

ftiasch has (n) items with volumes (w_1, w_2, \dots, w_n). Unfortunately, due to a mishap, the (i)-th item is lost. The task is to determine the number of ways to exactly fill a knapsack of capacity (x) using the remaining (n-1) items (each item can be used at most once). We denote the answer as (\text{cnt}(i, x)).

Given (n) and (m), compute (\text{cnt}(i, x)) for all (i \in [1,n]) and (x \in [1,m]).

Note: A subset is chosen from the remaining items such that the sum of their volumes equals exactly (x).

inputFormat

The first line contains two integers (n) and (m) --- the number of items and the maximum capacity respectively.<br> The second line contains (n) integers (w_1, w_2, \dots, w_n), where (w_i) represents the volume of the (i)-th item.

outputFormat

Output (n) lines. The (i)-th line should contain (m) integers (\text{cnt}(i,1), \text{cnt}(i,2), \dots, \text{cnt}(i,m)) separated by spaces, where (\text{cnt}(i,x)) is the number of ways to exactly fill a knapsack of capacity (x) after removing the (i)-th item.

sample

3 4
1 2 3

0 1 1 0
1 0 1 1
1 1 1 0