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.186s 0.010s 13