Problem B. Breaking digits

Author:A. Klenin   Time limit:1 sec
Input file:input.txt   Memory limit:256 Mb
Output file:output.txt  

Statement

Given an integer number A in decimal notation, your program must divide its digits between two integers B and C so that:

  1. Every digit of A is encountered exactly once in either B or C.
  2. The sum B + C is maximum possible.

Input file format

Input file contains a single integer A.

Output file format

Output file must contain two integers B and C. If there is more than one solution, output any of them.

Constraints

10 ≤ A ≤ 109

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
11
1
1
2
439
94
3
3
1000
100
0

0.086s 0.010s 13