Reconstructing the Hidden Set

Little Q once posted a challenge on his personal page: given a non-empty set \(S\) of positive integers (with each element not exceeding \(n\)) satisfying some extra conditions, one can easily compute for every positive integer \(x\) not exceeding \(n\) the number of ways \(f(x)\) to represent \(x\) as a sum of elements from \(S\) (each number can be used arbitrarily many times, and the order is ignored). For example, if \(S=\{1,2,3,4,5\}\) then one may obtain \(f(2)=2,\; f(3)=3,\; f(4)=5,\; f(5)=7\); while if \(S=\{1,2,5\}\) then \(f(4)=3,\; f(5)=4,\; f(6)=5,\; f(7)=6\>.

Sadly, Little Q has forgotten the actual elements of \(S\), but fortunately his storage device contains all the values of \(f(i)\bmod p\) for \(i=1,2,\dots,n\), where \(p\) is a prime. Your task is to recover a set \(S\) (with every element \(\le n\)) such that for every \(i=1,2,\dots,n\) the number of ways to represent \(i\) as a sum of elements from \(S\) is congruent to the given \(f(i)\) modulo \(p\). It is guaranteed that at least one such \(S\) exists.

Note that the stored data may correspond to more than one possible set. Among all possible solutions, output the one that is lexicographically smallest. We define the lexicographical order of two different sets \(S_1\) and \(S_2\) in the following way: Let the two sets be sorted in increasing order. Then \(S_1\) is lexicographically smaller than \(S_2\) if there exists a nonnegative integer \(k\) such that the first \(k\) smallest elements of \(S_1\) and \(S_2\) are identical, but either \(S_1\) has exactly \(k\) elements while \(S_2\) has at least \(k+1\) elements, or both sets have at least \(k+1\) elements and the \((k+1)\)th element of \(S_1\) is smaller than the \((k+1)\)th element of \(S_2\).

Hint: Let the generating function
\[ F(x)=\sum_{i\ge 0} f(i)x^i = \prod_{s\in S}\frac{1}{1-x^s}, \] with \(f(0)=1\). Taking the reciprocal, we have
\[ G(x)=1/F(x)=\prod_{s\in S}(1-x^s)= 1+g(1)x + g(2)x^2+\cdots. \]

You can first compute \(g(0)=1\) and for \(i\ge 1\) use the recurrence \[ g(i) = -\sum_{j=1}^{i} f(j)g(i-j) \pmod{p}, \] then use the fact that every factor \((1-x^s)\) contributes a \(-x^s\) term. In other words, if \(s\) is the smallest index (\(\ge1\)) for which the coefficient of \(x^s\) in \(G(x)\) is nonzero, it must come from the factor \((1-x^s)\). After finding such an \(s\), remove the factor \((1-x^s)\) from \(G(x)\) by polynomial division and repeat. This yields the lexicographically smallest \(S\).

inputFormat

The first line contains two integers \(n\) and \(p\) (where \(p\) is a prime). The second line contains \(n\) integers: \(f(1), f(2), \dots, f(n)\), where each \(f(i)\) is given modulo \(p\).

outputFormat

Output the elements of the lexicographically smallest set \(S\) (each \(\le n\)) in increasing order, separated by spaces.

sample

5 1000003
1 2 3 5 7

1 2 3 4 5