Sum over Derangements with Cycle Polynomial

Given two integers n and k, and a polynomial F(x) of degree k-1 defined by its coefficients, you are to compute for each integer m (1 ≤ m ≤ n):

Here, the sum is taken over all derangements \(\pi\) of length m (i.e. permutations with no fixed point, namely \(\pi_i \neq i\) for all i), and \(\mathrm{cyc}(\pi)\) denotes the number of cycles in the disjoint cycle decomposition of \(\pi\). The polynomial is given by

Your task is to output S(m) for each m from 1 to n, one per line.

inputFormat

The first line contains two integers n and k.

The second line contains k integers: a₀, a₁, ..., a_k-1, which are the coefficients of the polynomial F(x) in increasing order of degree.

outputFormat

Output n lines. The m-th line (1-indexed) should contain the value of S(m), the sum of F(\(\mathrm{cyc}(\pi)\)) over all derangements \(\pi\) of length m.

sample

3 1
1

0
1
2