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 sunuke_sum(arg):
    sum_digit = 0
    for char in arg:
        sum_digit += int(char)
    return sum_digit


input_num = int(input())

sunuke_dict = {}

min_sunuke_div = 10 ** 20
for d in reversed(range(1, 16)):
    for n in reversed(range(10, 1000)):
        i = n * (10 ** d) + (10 ** d - 1)
        sunuke_div = i / sunuke_sum(str(i))
        sunuke_dict[i] = sunuke_div

for i in reversed(range(1, 110)):
    sunuke_div = i / sunuke_sum(str(i))
    sunuke_dict[i] = sunuke_div

sunuke_sorted = sorted(sunuke_dict.items())
sunuke_list = []

for value, div_value in reversed(sunuke_sorted):
    if min_sunuke_div >= div_value:
        sunuke_list.append(value)
        min_sunuke_div = div_value

sunuke_list.reverse()

for i in range(0, input_num):
    print(str(sunuke_list[i]))