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.

Sample Input 1

10

Sample Output 1

1
2
3
4
5
6
7
8
9
19