Math is a Physical Education Subject 3

Interview

Time limit1sMemory limit1024 MB

Summary

Given the concatenation of all integers from A to B, recover A and B, choosing the smallest A if several pairs fit.

Level: Medium4 of 10
Topics: String, Brute force, Implementation, Math
Solved: No attempts yet

Problem

Ihwan is a genius five-year-old baby living in the era of the Fourth Industrial Revolution. One day, after discovering Ihwan's genius, his kindergarten teacher gave him the following problem.

What is the sum of all integers from $A$ to $B$ , inclusive?

Ihwan is a genius, but he is still a baby and does not really know what addition is. The next day, Ihwan wrote all the integers from $A$ to $B$ , inclusive, in increasing order with no spaces in his notebook. For example, when $A = 4$ and $B = 21$ , the answer Ihwan wrote down is 456789101112131415161718192021.

Ihwan is a genius with exceptional obsession over assignments, but his teacher is not. In fact, Ihwan's teacher even forgot what the two numbers he called yesterday were. The only information the teacher remembers is that both $A$ and $B$ were integers between $1$ and $999$ , inclusive, and that naturally $A$ was less than or equal to $B$ .

Given the sequence of digits Ihwan wrote down, can you find the two numbers the teacher called?

Input

The first line gives the string $S$ representing the answer Ihwan wrote down. $S$ consists only of digits (0123456789), and its length is between $1$ and $2\ 889$ , inclusive.

Output

Print the two integers $A$ and $B$ that Ihwan's teacher called, separated by a space. If more than one answer is possible, print the one with the smallest $A$ .

Because Ihwan always writes the correct answer, only inputs for which an answer satisfying the problem's conditions exists are given.

Examples4

Example 1
Input
```
9101112
```
Expected output
```
9 12
```
Example 2
Input
```
12
```
Expected output
```
1 2
```
Example 3
Input
```
999
```
Expected output
```
999 999
```
Example 4
Input
```
456789101112131415161718192021
```
Expected output
```
4 21
```