I. IabadaMalu
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Long ago, the IabadaMalu numeral system was widely used and had a special feature. To represent a number in the decimal system, one needed a number of sticks equal to the sum of that number's digits.

The IabadaMalu numeral system follows the same order as the decimal system, but with one change: A number belongs to the IabadaMalu system only if it is an integer and is also the smallest number that requires its given number of sticks—that is, the smallest number whose digits add up to that sum in the decimal system.

Amorim, a lover of numbers who has a special appreciation for ancient number systems, would like to know what the $$$K$$$-th number in the IabadaMalu number system is. To find this out, he has asked you to write a program that prints this number.

Input

The first and only line contains an integer $$$K$$$ $$$(1 \le K \le 10^6)$$$, which is the position of a number in the IabadaMalu numeral system.

Output

Print a single integer: the number at position $$$K$$$ in the IabadaMalu numeral system.

Examples
Input
3
Output
3
Input
7
Output
7
Input
16
Output
79