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 int long long

vector<int> ans;

int S(int x) {
        int ret = 0;
        while(x) {
                ret += x % 10;
                x /= 10;
        }
        return ret;
}


bool verify(int x, int y) {
        return x * S(y) < y * S(x);
}

void insert(int x) {
        while(verify(x, ans.back()))
                ans.pop_back();
        ans.push_back(x);
}

void init() {
        ans.push_back(1);
        for(int i = 2; i < 10000; i++) {
                insert(i);
        }
        for(int idx = 0, base = 10; idx < 12; idx++, base *= 10) {
                for(int i = 1000; i < 10000; i++)
                        insert(i * base + (base - 1));
        }
}

int32_t main() {
        cin.tie(0);
        cin.sync_with_stdio(0);
        init();

        int K;
        cin >> K;
        for(int i = 0; i < K; i++) {
                cout << ans[i] << '\n';
        }
}
