The Length of the Sequence

Time limit1sMemory limit1024 MB

Summary

Given a total digit count S, find the longest run of consecutive non-negative integers whose concatenated decimal form has exactly S digits, or report -1.

Level: Medium6 of 10
Topics: Math, Greedy
Solved: No attempts yet

Problem

Consider the non-negative integers from $l$ to $r$ . Write them in a row in decimal notation, getting a string $a$ . For example, if $l=3$ and $r=10$ , then $a=345678910$ .

Find a segment of consecutive non-negative integers $[l,r]$ ( $0 \le l \le r \le 10^{18}$ ) such that the length of the string $a$ is exactly $S$ and the number of integers in the segment is as large as possible.

Input

The only line contains one integer $S$ ( $1 \le S \le 10^{18}$ ).

Output

Print the length of the optimal segment in the first line. If there is no solution, print $-1$ .

If a solution exists, print two integers $l$ and $r$ on the second line. If there are multiple optimal solutions, print any of them.

Examples3

Example 1
Input
```
3
```
Expected output
```
3
0 2
```
Example 2
Input
```
10
```
Expected output
```
10
0 9
```
Example 3
Input
```
20
```
Expected output
```
15
0 14
```