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
#include<iostream>
#include<algorithm>
using namespace std;

int main(){
	long long n0,n1,n2;
	long long step;
	long long k;
	long long temp,wa;
	double dtmp0,dtmp1,dtmp2;
	

	cin >> k;
	int i=1;
	while(k>0 && i<10){
		cout << i <<endl;
		i++;
		k--;
	}
	if(k>0){
		cout << 19 << endl;
		k--;
	}
	
	step = 10;
	n0=19;
	n1=29;
	//dtmp1=
	dtmp0=1.9;
	dtmp1=29./11.;
	while(k>0){
		n2 = n1 + step;
		
		temp = n2;
		wa=0;
		while (temp>0){
			wa += temp%10;
			temp /= 10;
		}
		dtmp2 = (double)n2/(double)wa;
		// cout <<n0<<" "<<dtmp0<<" "<< n1 << " " << dtmp1 << " " << n2 << " "<<dtmp2<< " "<<step<<endl;
		if(dtmp2>=dtmp1){
			k--;
			cout << n1 << endl;
			step = n1 - n0;
			n0 = n1;
			dtmp0=dtmp1;
			n1 += step;
			temp = n1;
			wa=0;
			while (temp>0){
				wa += temp%10;
				temp /= 10;
			}
			dtmp1 = (double)n1/(double)wa;
		}else{
			//cout << "else"<<endl;
		
			n1 = n2;
			dtmp1=dtmp2;
		}
		
		
	}
	
	return 0;
}