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;

using ll = long long;

// 各桁の数の和
int digitSum(ll x) {
  int sum = 0;
  while (x > 0) {
    sum += x % 10;
    x /= 10;
  }
  return sum;
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  
  int k;
  cin >> k;
  
  vector<ll> x;
  for (ll i = 0; i < 15; i++) {
    ll keep = pow(10, i);
    for (ll j = 1; j <= 999; j++) {
      x.emplace_back(keep * j + keep - 1);
    }
  }
  
  sort(x.begin(), x.end());
  x.erase(unique(x.begin(), x.end()), x.end());
  
  vector<bool> judge(x.size(), true);
  for (int i = 0; i < x.size() - 1; i++) {
    for (int j = i + 1; j < x.size(); j++) {
      if ((double) x.at(i) / digitSum(x.at(i)) > (double) x.at(j) / digitSum(x.at(j))) {
        judge.at(i) = false;
        break;
      }
    }
  }
  
  int it = 0;
  for (int i = 0; i < k; i++) {
    while (!judge.at(it)) it++;
    cout << x.at(it) << '\n';
    it++;
  }
}