Problem: Suppose you have a sequence of k integers A = [a_1, a_2, ... , a_k] where each a_i ≥ 2. A sequence of prime integers P = [p_1, p_2, ..., p_k] is called suitable for the sequence A if a_1 is divisible by p_1, a_2 is divisible by p_2 and so on. 

A sequence of prime integers P is called friendly if there are no unique integers in this sequence. 

A sequence A is called ideal, if each sequence P that is suitable for A is friendly as well (i. e. there is no sequence P that is suitable for A, but not friendly). For example, the sequence [2, 4, 16] is ideal, while the sequence [2, 4, 6] is not ideal (there exists a sequence P = [2, 2, 3] which is suitable for A, but not friendly).

You are given n different integers x_1, x_2, ..., x_n. You have to choose exactly k of them in such a way that they form an ideal sequence, or report that it is impossible. Note that no integer can be chosen more than once.

Input

The first line contains two integers n and k (1 ≤ k ≤ n ≤ 1000). 

The second line contains n pairwise distinct integers x_1, x_2, ..., x_n (2 ≤ x_i ≤ 10^{18}).

Output

If it is impossible to choose exactly k integers from x_1, x_2, ..., x_n in such a way that the chosen integers form an ideal sequence, print 0.

Otherwise, print k pairwise distinct integers — the elements of the chosen ideal sequence. If there are multiple answers, print any of them.

Examples

Input

3 3
2 4 6


Output

0


Input

3 3
2 4 16


Output

2 4 16 


Input

4 3
2 4 6 16


Output

2 4 16 

Solution (in CPP):

Solution:
#include <bits/stdc++.h>

using namespace std;
const long long c=1002, gy=4e5, h=1e18;
long long n, k, t[c], prh[c], cnt;
bool v[c];
vector<pair<long long, long long> > pr;
vector<long long> alap;
map<long long, long long> m;
long long calc(long long x) {
    for (long long i=2; i<=gy; i++) {
        if (x%i==0) {
            while (x%i==0) {
                x/=i;
            }
            if (x==1) {
                return i;
            }
            return 0;
        }
    }
    return x;
}
int main()
{
    cin >> n >> k;
    for (int i=1; i<=n; i++) {
        cin >> t[i];
    }
    sort(t+1, t+n+1);
    for (int i=1; i<=n; i++) {
        long long x=m[t[i]];
        if (x) {
            //cout << "mar volt\n";
            if (!v[x]) {
                //cout << "uj prim\n";
                v[x]=1;
                alap.push_back(prh[x]);
                pr.push_back({prh[x], t[x]});
                v[i]=1;
                pr.push_back({prh[x], t[i]});
            }
            continue;
        }
        prh[i]=calc(t[i]);
        if (prh[i]) {
            long long x=prh[i], ert=x;
            while (h/x>=ert) {
                ert*=x;
                m[ert]=i;
            }
        }
    }
    cnt=pr.size();
    if (k>=cnt) {
        for (int i=1; i<=n; i++) {
            if (!v[i] && cnt<k) {
                long long x=t[i];
                for (long long oszt:alap) {
                    while (x%oszt==0) {
                        x/=oszt;
                    }
                }
                if (x==1) {
                    v[i]=1;
                    cnt++;
                }
            }
        }
        if (cnt<k) {
            cout << 0 << "\n";
        } else {
            for (int i=1; i<=n; i++) {
                if (v[i]) {
                    cout << t[i] << " ";
                }
            }
            cout << "\n";
        }
    } else {
        if (k%2==0) {
            for (int i=0; i<k; i++) {
                cout << pr[i].second << " ";
            }
            cout << "\n";
            return 0;
        }
        for (int i=1; i<=n; i++) {
            if (!v[i]) {
                long long x=t[i];
                int si=0;
                set<long long> s;
                for (long long oszt: alap) {
                    if (x%oszt==0) {
                        s.insert(oszt);
                        si++;
                    }
                    while (x%oszt==0) {
                        x/=oszt;
                    }
                }
                if (x==1 && 2*si<k) {
                    cout << t[i] << " ";
                    k--;
                    for (auto id:pr) {
                        long long fi=id.first, se=id.second;
                        if (s.find(fi)!=s.end()) {
                            cout << se << " ";
                            k--;
                        }
                    }
                    for (auto id:pr) {
                        long long fi=id.first ,se=id.second;
                        if (k && s.find(fi)==s.end()) {
                            cout << se << " ";
                            k--;
                        }

                    }
                    cout << "\n";
                    return 0;
                }
            }
        }
        cout << "0\n";
    }
    return 0;
}
/*
7 7
4 8
998244353
625 3125
996491788296388609
9982443530000
*/