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
import java.util.Scanner;

public class Main {
	
	public static double compute(long l) {
		long sum = 0;
		long t = l;
		while (t > 0) {
			sum += t % 10;
			t /= 10;
		}
		return (double)l / sum;
	}
	
	public static void main(String[] args) {
		Scanner s = new Scanner(System.in);
		int k = s.nextInt();
		
		long current = 1;
		for (int i = 0; i < k; i++) {
			double min = Double.MAX_VALUE;
			long next = -1; 
			String currentString = current + "";
			for (int j = 0; j < currentString.length() + 1; j++) {
				String ender = "";
				for (int m = 0; m < j; m++) {
					ender += "9";
				}
				String temp = currentString.substring(0, currentString.length() - j) + ender;
				long tempVal = new Long(temp);
				double ans = compute(tempVal);
				if (ans < min) {
					min = ans;
					next = tempVal;
				}
			}
			System.out.println(next);
			current = next + 1;
		}
	}

}
