Making Primes

Time limit2sMemory limit128 MB

Summary

Combine all N (up to 6) given numbers with +,-,*,/ and parentheses in every possible way to find the smallest and largest prime value obtainable.

Level: Medium6 of 10
Topics: Backtracking, Brute force, Math, Combinatorics
Solved: No attempts yet

Problem

You are given an array A of size N, filled with integers from 1 to 30 inclusive. Use every element exactly once, together with any number of +, -, *, /, and parentheses, to build one expression. Among all values that can be made, find the smallest prime and the largest prime.

Values in A may repeat.

For example, if A = {1, 2, 3}, the smallest prime is 3 - 2 + 1 = 2, and the largest prime is 3 * 2 + 1 = 7.

A division operation may be used only when both operands are positive integers and the division is exact; its result is the integer quotient.

Input

The first line contains the size N of array A. The second line contains the N elements of A, separated by spaces.

Output

Print the smallest prime that can be made on the first line, and the largest prime on the second line. If no prime can be made, print only -1.

Constraints

1 ≤ N ≤ 6

Examples6

Example 1
Input
```
2
1 2
```
Expected output
```
2
3
```
Example 2
Input
```
3
1 2 3
```
Expected output
```
2
7
```
Example 3
Input
```
6
1 2 3 4 5 6
```
Expected output
```
2
719
```
Example 4
Input
```
6
2 3 5 7 11 13
```
Expected output
```
2
15017
```
Example 5
Input
```
6
2 2 2 2 2 2
```
Expected output
```
2
17
```
Example 6
Input
```
1
8
```
Expected output
```
-1
```