Practice Greedy algorithms and String manipulation with the exercise "Rearrange string to two numbers"

Learning Opportunities

This puzzle can be solved using the following concepts. Practice using these concepts and improve your skills.

Greedy algorithms
String manipulation

Statement

Goal

You must rearrange the digits in the string S into two numbers A and B according to the following rules:
0 ≤ A, B ≤ 10^18;
No leading 0's. "0" is a valid number; "000" is not;
Minimize A, then minimize B.

Source: BSUIR Open Programming Championship

Input

The first and the only line contains string S consisting of digits only.

Output

Output two numbers A and B separated by space. If such numbers can't be formed then output -1 -1.

Constraints

1 ≤ length of S ≤ 50
0 ≤ A, B ≤ 10^18

Example

Input

Output

2 7

Solve it

A higher resolution is required to access the IDE