Background

Special for beginners, ^_^

Description

现在有一个19位的密码锁，初始为19个0，任何一位转动一格都需要耗费体力值1，只能从0-1-2这样转到9，不能反转。如果从19个0转动到某个数（可以看作财富值），定义财富值 / 耗费的体力为财力比。

显然存在一些坑数。任何比坑数大的数的财力比都不小于坑数。

现在给出k，请输出前k个坑数。

Format

Input

第一行一个正整数 $k（\le1300）$。

Output

输出前 $k$ 个坑数，一行一个。

Samples

10

1
2
3
4
5
6
7
8
9
19

Limitation

1s, 1024KiB for each test case.