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>
#define MAX_N 100001
#define INF_INT 2147483647
#define INF_LL 9223372036854775807
#define REP(i,n) for(int i=0;i<(int)(n);i++)
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> P;
const int MOD = 1000000007;

ll dsum(ll n){
  if( n == 0)
    return 0;
  else
    return n%10 + dsum(n/10);

}

int main()
{
  ll K;
  vector<ll> snukekoho(0),snuke(0);
  cin >> K;
  for(ll i=1;i<1000;i++){
    for(ll k=0;k<15;k++){
      ll dd = 1;
      REP(f,k)dd *= 10; 
      snukekoho.push_back(i*(dd)-1);
    }
  }
  sort(snukekoho.begin(),snukekoho.end());
  double d=(double)snukekoho[snukekoho.size()-1]/(double)dsum(snukekoho[snukekoho.size()-1]);
  for(int i=snukekoho.size()-2;i>=0;i--){
    double a = (double)snukekoho[i]/(double)dsum(snukekoho[i]);
      if(d > a){
        d = a;
        snuke.push_back(snukekoho[i]);
      }
  }
  REP(i,8)snuke.push_back(i+1);
  sort(snuke.begin(),snuke.end());
  REP(i,K){
    cout << snuke[i] << endl;
  }
  
  return 0;
}

