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.

Example

Input

10


Output

1
2
3
4
5
6
7
8
9
19
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <algorithm>
#include <vector>
 
int main(int argc, char* argv[])
{
    long kk;
    scanf("%ld", &kk);

    long long save = 0;
    long long tmp = 0;
    long count = 0;
    long i, j, k;
    for(i=0; i<16; i++) {
        for(j=1; ; j++) {
            long sum = 0;
            tmp = j;
            {
                long a = j;
                while(a>0) {
                    sum += (a%10);
                    a /= 10;
                }
            }
            for(k=0; k<i; k++) {
                tmp = tmp*10+9;
                sum += 9;
            }
            if( (double)tmp / sum > pow((double)10, i) ) {
                break;
            }
            if(save>=tmp) {
                continue;
            }

            printf("%lld\n", tmp);
            count ++;
            if(count==kk) {
                return 0;
            }
            save = tmp;
        }
    }
 
    return 0;
}