Description

In 1949, Indian mathematician D. R. Daprekar discovered a class of numbers called Self-Numbers. For every positive integer $n$, we define $d(n)$ as $n$ plus the sum of its digits. For example, $d(75) = 75 + 7 + 5 = 87$. Given any positive integer $n$ as a starting point, we can construct an infinite increasing sequence: $n, d(n), d(d(n)), d(d(d(n))), \ldots$ For example, if you start from $33$, the next number is $33 + 3 + 3 = 39$, the next is $39 + 3 + 9 = 51$, and the one after that is $51 + 5 + 1 = 57$, so the sequence you generate looks like this: $33, 39, 51, 57, 69, 84, 96, 111, 114, 120, 123, 129, 141, \ldots$ The number $n$ is called a generator of $d(n)$. In the sequence above, $33$ is a generator of $39$, $39$ is a generator of $51$, $51$ is a generator of $57$, and so on. Some numbers have more than one generator, such as $101$, whose generators can be $91$ and $100$. A number with no generator is called a Self-Number. The first $13$ Self-Numbers are $1, 3, 5, 7, 9, 20, 31, 42, 53, 64, 75, 86, 97$. We denote the $i$-th Self-Number by $a_i$, so $a_1 = 1, a_2 = 3, a_3 = 5, \ldots$.

Input Format

The input contains integers $N, K, s_1, \ldots, s_K$, where $1 \le N \le {10}^7$ and $1 \le K \le 5000$, separated by spaces and newlines.

Output Format

On the first line, output a single number: the count of Self-Numbers in the closed interval $[1, N]$. The second line must contain $K$ numbers separated by spaces, namely $a_{s_1}, \ldots, a_{s_K}$. It is guaranteed that all of $a_{s_1}, \ldots, a_{s_K}$ are less than $N$. (For example, if $N = 100$, $s_k$ can be from $1$ to $13$, but not $14$, because $a_{14} = 108 > 100$.)

100 10
1 2 3 4 5 6 7 11 12 13 

13
1 3 5 7 9 20 31 75 86 97

Hint

For $100\%$ of the testdata, $1 \le N \le {10}^7$ and $1 \le K \le 5000$.

Translated by ChatGPT 5