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;
typedef long long ll;
#define st first
#define nd second

const int MX = 1e6+2;
vector<ll> primes;
bool isComposite[MX];
void sieve() {
    for(int i=2;i<MX;i++) {
        if(isComposite[i])
            continue;
        primes.push_back(i);
        for(int j=2*i;j<MX;j+=i)
            isComposite[j] = 1;
    }
}

ll slow_mul(ll a, ll b, ll mod) {
    if(b == 0)
        return 0;
    if(b&1)
        return (slow_mul(a,b-1,mod)+a)%mod;
    ll tmp = slow_mul(a,b/2,mod);
    return (tmp + tmp)%mod;
}

ll fme(ll a, ll b, ll mod) {
    if(b == 0)
        return 1;
    if(b&1)
        return slow_mul(fme(a,b-1,mod),a,mod);
    ll tmp = fme(a,b/2,mod);
    return slow_mul(tmp,tmp,mod);
}


bool mr(ll a, ll k, ll s) {
    ll n = k*(1LL<<s)+1;
    ll x = fme(a,k,n);
    bool prime = true;
    for(int i=0;i<=s;i++) {
        if(x == n-1)
            prime = true;
        else if(x != 1)
            prime = false;
        if(i != s)
            x = slow_mul(x,x,n);
    }
    return prime && x == 1;
}

bool isPrime(ll n) {
    if(n == 1) return false;
    ll k=n-1,s=0;
    while(!(k&1))
        k/=2, s++;
    for(auto a : {2, 3, 5, 7, 11, 13, 17, 19, 23}) {
        a %= n;
        if(a == 0)
            continue;
        if(!mr(a,k,s))
            return false;
    }
    return true;
}


int32_t main(){
    ios::sync_with_stdio(false);
    sieve();
    int n,k;
    cin >> n >> k;
    if(k == 1) {
        cout<<"0\n";
        return 0;
    }
    vector<pair<pair<ll,ll>,vector<ll> > > tab;
    vector<ll> nt;
    map<ll,vector<ll> > mp;
    for(int i=0;i<n;i++) {
        ll x, xo;
        cin >> x;
        xo = x;
        vector<ll> r;
        for(auto p : primes) {
            if(x%p == 0)
                r.push_back(p);
            
            while(x % p == 0)
                x /= p;
            if(p*p >= x)
                break;
        }
        if(x != 1) {
            for(ll a = sqrtl(x)-2;a <= sqrtl(x)+2;a++) {
                if(a*a == x) {
                    x = 1;
                    r.push_back(a);
                    break;
                }
            }
        }
        if(isPrime(x)) {
            r.push_back(x);
            x = 1;
        }
        if(x == 1 && r.size() == 1) {
            mp[r[0]].push_back(xo);
        }
        else 
            tab.push_back({{x,xo},r});
    }
    pair<pair<ll,ll>,vector<ll> > best = {{-1,-1},vector<ll>(66)};

    for(auto it = mp.begin();it != mp.end(); ) {
        auto c = it;
        it++;
        if(c->nd.size() <= 1)
            mp.erase(c);
    }

    for(auto a:tab) {
        if(a.st.st != 1) {
            for(auto kv:mp) {
                if(a.st.st % kv.st == 0) {
                    a.st.st = 1;
                    a.nd.push_back(kv.st);
                    a.nd.push_back(a.st.st/kv.st);
                    break;
                }
            }
        }
        if(a.st.st == 1) {
            bool bad = false;
            for(auto d : a.nd) {
                if(!mp.count(d) || mp[d].size() == 1) {
                    bad = true;
                }
            }
            if(!bad) {
                nt.push_back(a.st.nd);
                if(a.nd.size() < best.nd.size())
                    best = a;
            }
        }
    }
    ll sw = -1;
    for(auto a:mp)
        if(a.nd.size() >= 3)
            sw = a.st;
    if(sw != -1) {
        vector<ll> res = mp[sw];
        if(res.size() >= k) {
            for(int i=0;i<k;i++)
                cout<<res[i]<<" ";
            return 0;
        }
        for(auto a:mp) {
            if(a.st == sw)
                continue;
            if(res.size()+1 == k) {
                res.erase(res.begin());
            }

            while(res.size() < k && mp[a.st].size() > 0) {
                res.push_back(mp[a.st].back());
                mp[a.st].pop_back();
            }
            if(res.size() == k) {
                for(auto x:res)
                    cout<<x<<" ";
                return 0;
            }
        }
        while(nt.size() > 0 && res.size() < k) {
            res.push_back(nt.back());
            nt.pop_back();
        }
        if(res.size() == k) {
            for(auto a:res)
                cout<<a<<" ";
            return 0;
        }
        cout<<"0\n";
        return 0;
    }
    vector<ll> res;
    if(k%2 == 1) {
        if(best.st.st == -1 || best.nd.size()*2+1 > k) {
            cout<<"0\n";
            return 0;
        }
        res.push_back(best.st.nd);
        for(auto a:best.nd) {
            res.push_back(mp[a][0]);
            res.push_back(mp[a][1]);
            mp.erase(a);
        }
        nt.erase(find(nt.begin(),nt.end(),best.st.nd));
    }
    for(auto a:mp) {
        if(res.size() == k) {
            for(auto x:res)
                cout<<x<<" ";
            return 0;
        }
        res.push_back(a.nd[0]);
        res.push_back(a.nd[1]);
    }

    while(nt.size() > 0 && res.size() < k) {
        res.push_back(nt.back());
        nt.pop_back();
}
    if(res.size() == k) {
        for(auto a:res)
            cout<<a<<" ";
        return 0;
    }
    cout<<"0\n";
    return 0;
}