Numbers#3356

Numbers

1 second

64 megabytes

Very hard

Vasya wrote down all the numbers from $1$ to $X$ in sequence, without any spaces. Then, from each sequence of consecutive identical digits, he kept only one digit. As a result, $S$ digits remained. However, Vasya forgot the value of $X$ he initially used. Your task is to help him determine $X$ .

Input

The input consists of a single integer $S$ ( $1 \leq S \leq 1 0^{18}$ 1 \le S \le 10^{18}).

Output

The output should be a single integer $X$ . If no such number exists, output $- 1$ .

Examples

Example 1

Loading

1 \leq S \leq 1 0^{18}