問題文

天下一王国では整数は辞書順比較で表します。入国したばかりのダイキ君はとりあえず 1000 までの整数を書き出すことにしました。

1 以上 1000 以下のすべての整数を十進数で表した文字列を辞書順比較で昇順にソートして、1 行ずつ出力してください。

辞書順比較について

文字列 A に対して、 A_i で i 番目の文字を表し、 |A| で文字列 A の文字数を表すことにすると、文字列 A と文字列 B を辞書順比較で比較するとは、

• A_i \neq B_i となる最小の i (1 \leq i \leq {\rm min}(|A|,\ |B|)) に対して
• A_i \lt{} B_i であれば、文字列 A は文字列 B より小さい
• A_i \gt{} B_i であれば、文字列 A は文字列 B より大きい
• そのような i が存在しなければ、文字数が少ない方を小さいとする

として文字列 A と文字列 B の大小関係を決めることである。

例えば、 1, 2, 11, 12, 21 を辞書順比較で昇順にソートすると 1, 11, 12, 2, 21 となる。

1 から 10 までの出力例

1
10
2
3
4
5
6
7
8
9