Cow-abunga!

Interview

Time limit1sMemory limit1024 MB

Summary

Given at most 9 cow weights, choose M of them and print every prime number that appears as a subset sum, in increasing order.

Level: Medium4 of 10
Topics: Brute force, Combinatorics, Number theory, Sorting
Solved: No attempts yet

Problem

The winners of the last barn raffle have been announced. The cows that won the raffle were so happy they felt like flying, and then they actually flew into the sky. But after that, the cows could no longer fly. Then one day they realized that a bee sting lets them fly for a short while. Once this fact spread, the cows began flying freely through the sky again.

As the cows flew and cow traffic accidents became frequent, Farmer John restricted the cows' flying. The cows protested, but their protests were not accepted.

There are $N$ cows on the farm. Farmer John plans to select $M$ cows so that the sum of their weights is a prime number. Print every weight sum that can result from selecting cows according to Farmer John's plan.

Input

The first line gives the number of cows on the farm $N$ and the number of cows to select $M$ .

The second line gives the weights of the cows $H_i$ .

Output

Print, in increasing order, every prime number that can be made as the sum of the weights of $M$ cows. If no such case exists, print $-1$ .

Constraints

$1 \le M \le N \le 9$
$1 \le H_i \le 1,000$

Examples1

Example 1
Input
```
5 3
2 4 10 5 8
```
Expected output
```
11 17 19 23
```