Maximum Product Partition

Given a multiset of digits (each digit is between \(0\) and \(9\)), you are to partition all the digits into two groups (each group may form a non‐negative integer by rearranging its digits in descending order – note that leading zeros are allowed) such that the product of the two resulting integers is maximized. Let the maximum product be \(p\). However, to avoid a trivial solution, it is required that it is not allowed that one of the two integers contains all the given digits (i.e. for at least one of the two outputs, the frequency count of some digit differs from the input frequency). (In other words, if one outputs a solution in which one integer exactly uses all the given digits and the other is \(0\), you will only obtain half score.)

Your task is to find two non‐negative integers \(A\) and \(B\) such that \(A\times B=p\) and the partition (i.e. the multiset of digits for each number) does not have one integer exactly equal to the entire input digit multiset.

Note: When forming an integer from a group of digits, you should arrange them in descending order to obtain the maximum possible value from that group.

For example, if the input digits are 1 2 3 (i.e. the multiset "123") then one optimal partition is to form \(A=21\) from digits {1,2} and \(B=3\) from {3} so that \(21 \times 3=63\), which is the maximum possible product.

inputFormat

The input consists of a single line containing a non-empty string of digits. These digits (each between 0 and 9) represent the multiset given as input.

outputFormat

Output two non‐negative integers separated by a space such that their product is equal to the maximum possible product \(p\) under the given restrictions. Note that the integers must be formed from a nontrivial partition (i.e. neither integer is allowed to have the same digit frequency as the entire input multiset).

sample

123

21 3