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
LEN = 0

SNK = [1,2,3,4,5,6,7,8,9]
#SNK.append("SUNUKE!:"+str(1))
LEN +=1

for i in range(1,10): SNK.append(i*10+9)
#SNK.append("SUNUKE!:"+str(2))
LEN +=1

#for i in range(1,10): SNK.append(i*100+99)
#SNK.append("SUNUKE!:"+str(3))
LEN +=1

for loop in range(2):
    SNK_sub = list(range(pow(10,loop),pow(10,loop+1)))
    SNK += list(map(lambda x:(x*pow(10,LEN-1))+(pow(10,LEN-1)-1),SNK_sub))
    LEN += len(str(max(SNK_sub)))-1
    for d in SNK_sub: #loop=0のとき，d=1-9
        SNK += [(i*pow(10,LEN-1))+(pow(10,LEN-1)-1) for i in range(10,10*(d+1))]
        SNK += list(map(lambda x:(x*pow(10,LEN))+(pow(10,LEN)-1),SNK_sub[SNK_sub.index(d)+1:]))
        #SNK.append("SUNUKE!:"+str(LEN+3))
        LEN += 1+loop
        if LEN>20:break

print("\n".join(str(i) for i in SNK[:int(input())]))