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 ≤ d_i ≤ 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