Ada and Digits 2
Ada the Ladybug likes numbers. Her friends know it so they wanted to give her a number as a gift. Sadly, they bought the number in IKEA so Ada has to assemble the number by herself. Now she is in following situation - she has a few digits before herself and she is wondering what number she will create. As she doesn't understand the manual (it is in Swedish) she has possibility to assemble anything.
She is not sure yet, anyway her favourite options are to assemble number with the most divisors or the number with the biggest sum of divisors. Can you help her to find such?
NOTE: To assemble number from digits, simply choose any permutation of digits. Leading zeroes are perfectly OK but you have to use all the digits.
Input
The first line of each test-case will contain an integer 1 ≤ N ≤ 9, the number of digits to assemble.
The next line will contain N digits 0 ≤ di ≤ 9 .
Output
Output two integers - the number with the most divisors AND the number with biggest sum of divisors. In case there are multiple such numbers, choose the lesser one. As long as you would use leading zeroes, output the number without the leading zeroes.
Example Input
1 5
Example Output
5 5
Example Input
3 1 1 0
Example Output
110 110
Example Input
2 3 4
Example Output
34 34
Example Input
5 1 2 3 4 5
Example Output
43512 51324
Example Input
6 2 2 3 3 4 4
Example Output
432432 432432
Example Input
3 4 8 2
Example Output
248 824
Example Input
4 1 3 5 7
Example Output
7315 7315
Example Input
7 1 2 3 4 5 6 7
Example Output
3124576 7516432