Minimal Total Sum with Equal Digit Sum

Little Petya loves integers. Recently he learned that if the sum of a number's digits is divisible by \(9\), then the number itself is divisible by \(9\). Now he is interested in a different property. He wants to find n distinct positive integers that all share the same digit sum (say, \(s\)) such that the total sum of these integers is minimized.

More formally, given a positive integer \(n\), choose a digit sum \(s\) and n distinct positive integers \(a_1, a_2, \dots, a_n\) satisfying:

[ \text{digit_sum}(a_1)=\text{digit_sum}(a_2)=\cdots=\text{digit_sum}(a_n)=s, ]

and such that the total sum \(a_1+a_2+\cdots+a_n\) is as small as possible. The numbers in the solution should be output in increasing order.

Note: The digit sum of a number is the sum of its decimal digits. For example, \(\text{digit\_sum}(123) = 1+2+3 = 6\).

inputFormat

The input consists of a single line containing a positive integer \(n\) \((1 \leq n \leq 50)\), the number of distinct positive integers you need to find.

outputFormat

Output a single line with n positive integers separated by spaces, arranged in increasing order, which are the chosen numbers having the same digit sum and having the minimal possible total sum.

sample

2

1 10