#include <cstdio>
#include <vector>
#include <queue>
#include <limits>
#include <algorithm>
using namespace std;
struct NetworkFlow {
struct Edge {
int target, inverse_index;
int capacity, flow;
Edge(int t, int c, int ii) : target(t), capacity(c), flow(0), inverse_index(ii) {}
int residual() const { return capacity - flow; }
};
int V;
vector< vector<Edge> > adj;
vector<int> levels, edges_tried;
NetworkFlow(int V) : V(V), adj(V), levels(V), edges_tried(V) {}
void add_edge(int a, int b, int a2b, int b2a = 0) {
int a2b_index = adj[a].size(), b2a_index = adj[b].size();
adj[a].push_back(Edge(b, a2b, b2a_index));
adj[b].push_back(Edge(a, b2a, a2b_index));
}
bool assign_levels(int source, int sink) {
fill(levels.begin(), levels.end(), -1);
queue<int> q; q.push(source);
levels[source] = 0;
while (!q.empty()) {
int here = q.front(); q.pop();
for (int i = 0; i < adj[here].size(); ++i) {
const Edge& e = adj[here][i];
if (levels[e.target] == -1 && e.residual() > 0) {
levels[e.target] = levels[here] + 1;
q.push(e.target);
}
}
}
return levels[sink] != -1;
}
int push_flow(int here, int sink, int flow) {
if (here == sink) return flow;
for (int& i = edges_tried[here]; i < adj[here].size(); ++i) {
Edge& e = adj[here][i];
if (e.residual() > 0 && levels[e.target] == levels[here] + 1) {
int amt = push_flow(e.target, sink, min(flow, e.residual()));
if (amt > 0) {
Edge& e_inv = adj[e.target][e.inverse_index];
e.flow += amt;
e_inv.flow = -e.flow;
return amt;
}
}
}
return 0;
}
int go(int source, int sink) {
int total_flow = 0;
while (assign_levels(source, sink)) {
fill(edges_tried.begin(), edges_tried.end(), 0);
while (true) {
int pushed = push_flow(source, sink, numeric_limits<int>::max());
if (pushed == 0) break;
total_flow += pushed;
}
}
return total_flow;
}
};
bool isprime[2005];
int main() {
int n;
for (int i = 2; i <= 2000; i++) isprime[i] = 1;
for (int i = 2; i <= 2000; i++) {
if (isprime[i] == 1) {
for (int j = i + i; j <= 2000; j += i) isprime[j] = 0;
}
}
scanf("%d", &n);
vector <int> v, res;
v.resize(n);
for (int i = 0; i < n; i++) scanf("%d", &v[i]);
for (int i = 1; i < n; i++) {
if (isprime[v[0] + v[i]]) {
vector <int> x;
x.push_back(0);
for (int k = 1; k < n; k++) {
if (k == i) continue;
x.push_back(v[k]);
}
int m = n - 2;
NetworkFlow f(2 * m + 2);
for (int k = 1; k <= m; k++) {
f.add_edge(0, k, 1, 0);
f.add_edge(m + k, 2 * m + 1, 1, 0);
for (int l = 1; l <= m; l++) {
if (k == l) continue;
if (isprime[x[k] + x[l]]) f.add_edge(k, m + l, 1, 0);
}
}
int flow = f.go(0, 2 * m + 1);
if (flow == m) res.push_back(v[i]);
}
}
sort(res.begin(), res.end());
if (res.size() == 0) puts("-1");
else {
for (int i = 0; i < res.size(); i++) {
printf("%d ", res[i]);
}
}
}
I2luY2x1ZGUgPGNzdGRpbz4KI2luY2x1ZGUgPHZlY3Rvcj4KI2luY2x1ZGUgPHF1ZXVlPgojaW5jbHVkZSA8bGltaXRzPgojaW5jbHVkZSA8YWxnb3JpdGhtPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwpzdHJ1Y3QgTmV0d29ya0Zsb3cgewoJc3RydWN0IEVkZ2UgewoJCWludCB0YXJnZXQsIGludmVyc2VfaW5kZXg7CgkJaW50IGNhcGFjaXR5LCBmbG93OwoJCUVkZ2UoaW50IHQsIGludCBjLCBpbnQgaWkpIDogdGFyZ2V0KHQpLCBjYXBhY2l0eShjKSwgZmxvdygwKSwgaW52ZXJzZV9pbmRleChpaSkge30KCQlpbnQgcmVzaWR1YWwoKSBjb25zdCB7IHJldHVybiBjYXBhY2l0eSAtIGZsb3c7IH0KCX07CglpbnQgVjsKCXZlY3RvcjwgdmVjdG9yPEVkZ2U+ID4gYWRqOwoJdmVjdG9yPGludD4gbGV2ZWxzLCBlZGdlc190cmllZDsKCglOZXR3b3JrRmxvdyhpbnQgVikgOiBWKFYpLCBhZGooViksIGxldmVscyhWKSwgZWRnZXNfdHJpZWQoVikge30KCgl2b2lkIGFkZF9lZGdlKGludCBhLCBpbnQgYiwgaW50IGEyYiwgaW50IGIyYSA9IDApIHsKCQlpbnQgYTJiX2luZGV4ID0gYWRqW2FdLnNpemUoKSwgYjJhX2luZGV4ID0gYWRqW2JdLnNpemUoKTsKCQlhZGpbYV0ucHVzaF9iYWNrKEVkZ2UoYiwgYTJiLCBiMmFfaW5kZXgpKTsKCQlhZGpbYl0ucHVzaF9iYWNrKEVkZ2UoYSwgYjJhLCBhMmJfaW5kZXgpKTsKCX0KCglib29sIGFzc2lnbl9sZXZlbHMoaW50IHNvdXJjZSwgaW50IHNpbmspIHsKCQlmaWxsKGxldmVscy5iZWdpbigpLCBsZXZlbHMuZW5kKCksIC0xKTsKCQlxdWV1ZTxpbnQ+IHE7IHEucHVzaChzb3VyY2UpOwoJCWxldmVsc1tzb3VyY2VdID0gMDsKCQl3aGlsZSAoIXEuZW1wdHkoKSkgewoJCQlpbnQgaGVyZSA9IHEuZnJvbnQoKTsgcS5wb3AoKTsKCQkJZm9yIChpbnQgaSA9IDA7IGkgPCBhZGpbaGVyZV0uc2l6ZSgpOyArK2kpIHsKCQkJCWNvbnN0IEVkZ2UmIGUgPSBhZGpbaGVyZV1baV07CgkJCQlpZiAobGV2ZWxzW2UudGFyZ2V0XSA9PSAtMSAmJiBlLnJlc2lkdWFsKCkgPiAwKSB7CgkJCQkJbGV2ZWxzW2UudGFyZ2V0XSA9IGxldmVsc1toZXJlXSArIDE7CgkJCQkJcS5wdXNoKGUudGFyZ2V0KTsKCQkJCX0KCQkJfQoJCX0KCQlyZXR1cm4gbGV2ZWxzW3NpbmtdICE9IC0xOwoJfQoKCWludCBwdXNoX2Zsb3coaW50IGhlcmUsIGludCBzaW5rLCBpbnQgZmxvdykgewoJCWlmIChoZXJlID09IHNpbmspIHJldHVybiBmbG93OwoKCQlmb3IgKGludCYgaSA9IGVkZ2VzX3RyaWVkW2hlcmVdOyBpIDwgYWRqW2hlcmVdLnNpemUoKTsgKytpKSB7CgkJCUVkZ2UmIGUgPSBhZGpbaGVyZV1baV07CgkJCWlmIChlLnJlc2lkdWFsKCkgPiAwICYmIGxldmVsc1tlLnRhcmdldF0gPT0gbGV2ZWxzW2hlcmVdICsgMSkgewoJCQkJaW50IGFtdCA9IHB1c2hfZmxvdyhlLnRhcmdldCwgc2luaywgbWluKGZsb3csIGUucmVzaWR1YWwoKSkpOwoJCQkJaWYgKGFtdCA+IDApIHsKCQkJCQlFZGdlJiBlX2ludiA9IGFkaltlLnRhcmdldF1bZS5pbnZlcnNlX2luZGV4XTsKCQkJCQllLmZsb3cgKz0gYW10OwoJCQkJCWVfaW52LmZsb3cgPSAtZS5mbG93OwoJCQkJCXJldHVybiBhbXQ7CgkJCQl9CgkJCX0KCQl9CgkJcmV0dXJuIDA7Cgl9CgoJaW50IGdvKGludCBzb3VyY2UsIGludCBzaW5rKSB7CgkJaW50IHRvdGFsX2Zsb3cgPSAwOwoJCXdoaWxlIChhc3NpZ25fbGV2ZWxzKHNvdXJjZSwgc2luaykpIHsKCQkJZmlsbChlZGdlc190cmllZC5iZWdpbigpLCBlZGdlc190cmllZC5lbmQoKSwgMCk7CgkJCXdoaWxlICh0cnVlKSB7CgkJCQlpbnQgcHVzaGVkID0gcHVzaF9mbG93KHNvdXJjZSwgc2luaywgbnVtZXJpY19saW1pdHM8aW50Pjo6bWF4KCkpOwoJCQkJaWYgKHB1c2hlZCA9PSAwKSBicmVhazsKCQkJCXRvdGFsX2Zsb3cgKz0gcHVzaGVkOwoJCQl9CgkJfQoJCXJldHVybiB0b3RhbF9mbG93OwoJfQp9Owpib29sIGlzcHJpbWVbMjAwNV07CmludCBtYWluKCkgewoJaW50IG47Cglmb3IgKGludCBpID0gMjsgaSA8PSAyMDAwOyBpKyspIGlzcHJpbWVbaV0gPSAxOwoJZm9yIChpbnQgaSA9IDI7IGkgPD0gMjAwMDsgaSsrKSB7CgkJaWYgKGlzcHJpbWVbaV0gPT0gMSkgewoJCQlmb3IgKGludCBqID0gaSArIGk7IGogPD0gMjAwMDsgaiArPSBpKSBpc3ByaW1lW2pdID0gMDsKCQl9Cgl9CglzY2FuZigiJWQiLCAmbik7Cgl2ZWN0b3IgPGludD4gdiwgcmVzOwoJdi5yZXNpemUobik7Cglmb3IgKGludCBpID0gMDsgaSA8IG47IGkrKykgc2NhbmYoIiVkIiwgJnZbaV0pOwoJZm9yIChpbnQgaSA9IDE7IGkgPCBuOyBpKyspIHsKCQlpZiAoaXNwcmltZVt2WzBdICsgdltpXV0pIHsKCQkJdmVjdG9yIDxpbnQ+IHg7CgkJCXgucHVzaF9iYWNrKDApOwoJCQlmb3IgKGludCBrID0gMTsgayA8IG47IGsrKykgewoJCQkJaWYgKGsgPT0gaSkgY29udGludWU7CgkJCQl4LnB1c2hfYmFjayh2W2tdKTsKCQkJfQoJCQlpbnQgbSA9IG4gLSAyOwoJCQlOZXR3b3JrRmxvdyBmKDIgKiBtICsgMik7CgkJCWZvciAoaW50IGsgPSAxOyBrIDw9IG07IGsrKykgewoJCQkJZi5hZGRfZWRnZSgwLCBrLCAxLCAwKTsKCQkJCWYuYWRkX2VkZ2UobSArIGssIDIgKiBtICsgMSwgMSwgMCk7CgkJCQlmb3IgKGludCBsID0gMTsgbCA8PSBtOyBsKyspIHsKCQkJCQlpZiAoayA9PSBsKSBjb250aW51ZTsKCQkJCQlpZiAoaXNwcmltZVt4W2tdICsgeFtsXV0pIGYuYWRkX2VkZ2UoaywgbSArIGwsIDEsIDApOwoJCQkJfQoJCQl9CgkJCWludCBmbG93ID0gZi5nbygwLCAyICogbSArIDEpOwoJCQlpZiAoZmxvdyA9PSBtKSByZXMucHVzaF9iYWNrKHZbaV0pOwoJCX0KCX0KCXNvcnQocmVzLmJlZ2luKCksIHJlcy5lbmQoKSk7CglpZiAocmVzLnNpemUoKSA9PSAwKSBwdXRzKCItMSIpOwoJZWxzZSB7CgkJZm9yIChpbnQgaSA9IDA7IGkgPCByZXMuc2l6ZSgpOyBpKyspIHsKCQkJcHJpbnRmKCIlZCAiLCByZXNbaV0pOwoJCX0KCX0KfQ==