410335: GYM104010 G The Length of the Sequence

Memory Limit:512 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

G. The Length of the Sequencetime limit per test1 secondmemory limit per test512 megabytesinputstandard inputoutputstandard output

Consider the segment of 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$$$, $$$a=345678910$$$.

You have to find such segment of consecutive non-negative integers $$$[l,r]$$$ ($$$0 \le l \le r \le 10^{18}$$$) that the length of the string $$$a$$$, corresponding to this segment, is exactly $$$S$$$, and the number of integers in the segment $$$[l,r]$$$ is maximum possible.

Input

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

Output

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

If the solution exists, print two integers $$$l$$$ and $$$r$$$ in the second line.

If there are multiple optimal solutions, print any of them.

ExamplesInput
3
Output
3
0 2
Input
10
Output
10
0 9
Input
20
Output
15
0 14

加入题单

上一题 下一题 算法标签: