问题描述

记 $S(n)$ 为十进制表示中数字 $n$ 的各个位数之和。例如，$S(123) = 1 + 2 + 3 = 6$。

我们将整数 $n$ 称为Snuke数，当且仅当对于所有满足 $m > n$ 的正整数 $m$，$\\frac{n}{S(n)} \\leq \\frac{m}{S(m)}$ 成立。

给定一个整数 $K$，列出前 $K$ 个最小的 Snuke 数。

约束条件

• $1 \leq K$
• 第 $K$ 小的 Snuke 数不超过 $10^{15}$。

输入

输入形式如下，从标准输入读取：

$K$

输出

打印 $K$ 行。第 $i$ 行应包含第 $i$ 个最小的 Snuke 数。

示例输入 1

10

示例输出 1

1
2
3
4
5
6
7
8
9
19