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
###############################################################################

from sys import stdout
from bisect import bisect_left as binl
from copy import copy, deepcopy
from collections import defaultdict


mod = 1


def intin():
    input_tuple = input().split()
    if len(input_tuple) <= 1:
        return int(input_tuple[0])
    return tuple(map(int, input_tuple))


def intina():
    return [int(i) for i in input().split()]


def intinl(count):
    return [intin() for _ in range(count)]


def modadd(x, y):
    global mod
    return (x + y) % mod


def modmlt(x, y):
    global mod
    return (x * y) % mod


def lcm(x, y):
    while y != 0:
        z = x % y
        x = y
        y = z
    return x


def combination(x, y):
    assert(x >= y)

    if y > x // 2:
        y = x - y

    ret = 1

    for i in range(0, y):
        j = x - i
        i = i + 1

        ret = ret * j
        ret = ret // i

    return ret


def get_divisors(x):
    retlist = []
    for i in range(1, int(x**0.5) + 3):
        if x % i == 0:
            retlist.append(i)
            retlist.append(x // i)
    return retlist


def get_factors(x):
    retlist = []
    for i in range(2, int(x**0.5) + 3):
        while x % i == 0:
            retlist.append(i)
            x = x // i
    retlist.append(x)
    return retlist


def make_linklist(xylist):
    linklist = {}
    for a, b in xylist:
        linklist.setdefault(a, [])
        linklist.setdefault(b, [])
        linklist[a].append(b)
        linklist[b].append(a)
    return linklist


def calc_longest_distance(linklist, v=1):
    distance_list = {}
    distance_count = 0
    distance = 0
    vlist_previous = []
    vlist = [v]
    nodecount = len(linklist)

    while distance_count < nodecount:
        vlist_next = []
        for v in vlist:
            distance_list[v] = distance
            distance_count += 1
            vlist_next.extend(linklist[v])
        distance += 1
        vlist_to_del = vlist_previous
        vlist_previous = vlist
        vlist = list(set(vlist_next) - set(vlist_to_del))

    max_distance = -1
    max_v = None
    for v, distance in distance_list.items():
        if distance > max_distance:
            max_distance = distance
            max_v = v

    return (max_distance, max_v)


def calc_tree_diameter(linklist, v=1):
    _, u = calc_longest_distance(linklist, v)
    distance, _ = calc_longest_distance(linklist, u)
    return distance


###############################################################################


k = 0

def print_ans(x):
    global k
    print(x)
    k -= 1
    if k <= 0:
        exit(0)
    return x


def s(n):
    ret = 0
    while n:
        ret += n % 10
        n = n // 10
    return ret


def get_anslist(base, msnum, pownum):
    do_break = False
    end = ((msnum + 10) // 10) * 10
    ret = []

    for i in range(msnum, end):
        m = base + i * (10**pownum)
        snuke = m / s(m)
        ret.append((m, snuke))
        if snuke >= (10**pownum):
            do_break = True
    return ret, do_break


def main():
    global k
    k = intin()
    max_print = -1

    for i in range(16):
        base = 0 if i == 0 else int('9' * i)
        msnum = 1
        if max_print >= base:
            msnum = (max_print - base) // (10**i) + 1
        anslist = []

        while True:
            part_anslist, do_break = get_anslist(base, msnum, i)
            anslist.append(part_anslist)
            if do_break:
                break
            msnum = ((msnum + 10) // 10) * 10

        for part_anslist in anslist:
            prev = None
            incr = True
            for ans, snuke in part_anslist:
                if prev is not None and snuke < prev:
                    incr = False
                prev = last = snuke
            if incr:
                for ans, snuke in part_anslist:
                    max_print = print_ans(ans)
            else:
                prev = None
                for ans, snuke in part_anslist:
                    if snuke <= last:
                        max_print = print_ans(ans)
                    if prev is not None and prev > snuke:
                        break
                    prev = snuke


if __name__ == '__main__':
    main()
