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
def digitsum(n):#nは正の整数、各位の和、許容は１０＾１０００
    if n<10:
        return n
    else:
        m=n//10
        return n%10+digitsum(m)

snuke=[]
for i in range(4,16):
    #i桁のsnuke数を調べる
    #10**i-1はsnuke数
    #上三桁以外は9で確定なので10**i-1から順に調べればよい
    snuke.append(10**i-1)
    min=10**i-1
    k=998
    while k>=100:
        test=k*10**(i-3)+10**(i-3)-1
        if min*digitsum(test)>=test*digitsum(min):
            snuke.append(test)
            min=test
        k-=1


snuke.append(999)
min=999
k=998
while k>0:
    if min*digitsum(k)>=k*digitsum(min):
        snuke.append(k)
        min=k
    k-=1

snuke.sort()

K=int(input())
for i in range(0,K):
    print(snuke[i])