D - Snuke Numbers

Score : $500$ points

Problem Statement

Let $S(n)$ denote the sum of the digits in the decimal notation of $n$. For example, $S(123) = 1 + 2 + 3 = 6$.

We will call an integer $n$ a Snuke number when, for all positive integers $m$ such that $m > n$, $\frac{n}{S(n)} \leq \frac{m}{S(m)}$ holds.

Given an integer $K$, list the $K$ smallest Snuke numbers.

Constraints

• $1 \leq K$
• The $K$-th smallest Snuke number is not greater than $10^{15}$.

Input

Input is given from Standard Input in the following format:

$K$

Output

Print $K$ lines. The $i$-th line should contain the $i$-th smallest Snuke number.

10

1
2
3
4
5
6
7
8
9
19