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<bits/stdc++.h>
using namespace std;
#define rep(i,x,y) for(int i=x;i<y;i++)
#define range(a) (a).begin(),(a).end()
#define print(A,x,n) rep(i,0,n){cout<<(i ? " ":"")<<A[i]x;}cout<<endl;
#define pprint(A,y,m,n) rep(j,0,m){print(A[j],y,n);}
const long mod=998244353;
const int siz=1e5;
const long inf=1e9;
int digit(long a){
    int res = 0;
    while(a > 0){
        res += a % 10;
        a /= 10;
    }return res;
}
int main(){
	int K; cin>>K;
    long a = 1, b = 0;
    set<long> st;
	rep(i,0,16){
        long t = b; int j = 0;
		while(t <= a * digit(t)){
            if(j % 10 != 9) st.insert(t);
            t += a; j++;
		}a *= 10; (b *= 10) += 9;
	}
    /*long t = *st.rbegin() + 1;
    for(auto it = st.rbegin(); it != st.rend(); it++){
        if((*it) * digit(t) > t * digit(*it)) cout<<*it<<endl;
        t = *it;
    }*/
    int cnt = 0; st.erase(0);
    for(long v:st){
        cout<<v<<endl;
        if(++cnt == K) break;
    }
}