D - 辞書順最小の数

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 200

問題文

10^{10^{10}} 以下のすべての正整数を、文字列として見たときに辞書順で小さい順に並べた列を考えます。この列の先頭から N 番目の整数を求めてください。

制約

  • 1 ≦ N ≦ 100,000

入力

入力は以下の形式で標準入力から与えられる。

N

出力

答えを出力せよ。


入力例 1

2

出力例 1

10