Permutation Inversions and Weighted Sum

Given two positive integers n and k, and a permutation π′ of length n (which is provided but not used in the calculation), consider all permutations π of the set {1,2,…,n}. For any permutation π, define its inversion count as

$$\text{inv}_{\pi} = \sum_{i=1}^{n}\sum_{j=i+1}^{n}[\pi_i > \pi_j]$$

and define its weight by

$$\text{val}_{\pi} = \prod_{i=1}^{n}\prod_{j=i+1}^{n}\pi_i^{[\pi_i > \pi_j]}$$

Your task is, for each m with 0 ≤ m ≤ k, to compute the sum

$$S(m)=\sum_{\pi \text{ with } \text{inv}_{\pi}=m} \text{val}_{\pi}.$$

Note: Although an extra permutation π′ is given in the input, it is not used in the computations.

inputFormat

The first line contains two positive integers n and k.

The second line contains n distinct integers representing a permutation of {1, 2, …, n} (π′). This permutation is provided but is not used in the computation.

outputFormat

Output k+1 space‐separated integers. The m-th integer (0-indexed) should be equal to S(m), which is the sum of val_π for all permutations π such that inv_π = m.

sample

3 3
1 2 3

1 5 15 18