E. Waso Number
time limit per test
0.25 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

A non-negative integer is called waso if, when written in base $$$10$$$ without leading zeros, its digits read from left to right form a non-decreasing sequence. For example, $$$0$$$, $$$5$$$, $$$19$$$, $$$122$$$ and $$$123444$$$ are waso, while $$$10$$$, $$$21$$$ and $$$102$$$ are not.

The waso numbers, sorted from smallest to largest, are: $$$$$$0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, \ldots, 19, 22, 23, \ldots, 99, 111, \ldots$$$$$$

Given an integer $$$k$$$, find the $$$k$$$-th smallest waso number (considering $$$0$$$ as the first one).

Input

The input consists of a single line with an integer $$$k$$$ ($$$1 \leq k \leq 10^{18}$$$).

Output

Print a single integer: the $$$k$$$-th waso number.

Note that the answer may have several hundred digits, so it does not fit in standard 64-bit integer types.

Examples
Input
1
Output
0
Input
11
Output
11
Input
1000000
Output
113334555668999
Note

Explanation for example 1

The first waso number is $$$0$$$.