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
//hinagata.cpp
/*includes*/
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <stdio.h>
#include <numeric>
#include <iomanip>
#include <limits>
/*namespace*/
using namespace std;
using ll= long long;
/*define macro*/
#define REP(i,n) for(int i=0;i<(n);i++)
#define REPi(i,a,b) for(int i=(a);i<(b);i++)
#define REPRi(i,a,b) for(int i=(a);i>(b);i--)
#define ALL(x) (x).begin(),(x).end()
int sumd(ll A){
    string S=to_string(A);
    ll size=S.size();
    ll ans=0;
    REP(i,size){
        ans+=S[i]-'0';
    }
    return ans;
}


int main(){
    int k;
    cin>>k;
    ll a=1;
    ll p=1;
    REP(i,k){
        cout<<a<<endl;
        ll c=a+p;
        ll d=a+p*10;
        if(c*sumd(d)<=d*sumd(c)){
            a=c;
        }else{
            a=d;
            p*=10;
        }
    }
}