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 int ll;
typedef unsigned long long int ull;
typedef long double ld;

#ifdef LOCAL
#define Gene template< class
#define Rics printer& operator,
Gene c> struct rge{c b, e;};
Gene c> rge<c> range(c i, c j){ return {i, j};}
struct printer{
    ~printer(){cerr<<endl;}
    Gene c >Rics(c x){ cerr<<boolalpha<<x; return *this;}
    Rics(string x){cerr<<x;return *this;}
    Gene c, class d >Rics(pair<c, d> x){ return *this,"(",x.first,", ",x.second,")";}
    Gene ... d, Gene ...> class c >Rics(c<d...> x){ return *this, range(begin(x), end(x));}
    Gene c >Rics(rge<c> x){
        *this,"["; for(auto it = x.b; it != x.e; ++it)
            *this,(it==x.b?"":", "),*it; return *this,"]";}
};
#define debug() cerr<<"LINE "<<__LINE__<<" >> ", printer()
#define dbg(x) "[",#x,": ",(x),"] "
#define tham getchar()
#endif

#define FASTIO ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define eq(x, y) (fabs((x)-(y))<error)
#define bt(i) (1LL<<(i))

mt19937_64 rng((unsigned)chrono::system_clock::now().time_since_epoch().count());
//const ll mod = ;
//const ld error = ;
const ld PI = acosl(-1);

//const int/ll inf = ;
const int nmax = 1e6+5;
///===========================================  template  =======================================================

map<ll, ll> allpow;

bool composite[nmax];
void precal(){
    for(int i = 2; i<nmax; i++){
        if(composite[i]) continue;

        ll tmp = i;
        tmp *= i;

        do{
            tmp *= i;
            allpow[tmp] = i;
        }while(tmp < ll(1e18)/i);


        for(int j = i+i; j<nmax; j+=i){
            composite[j] = true;
        }
    }
}

//using floating points
ull modmult(ull a, ull b, ull m){
    if(a >= m) a %= m;
    if(b >= m) b %= m;
    ull q = ull(ld(a)*b/m);
    ll r = ll(a*b-q*m) % ll(m);
    return r < 0? r+m: r;
}

ll modexpo(ll x, ll n, ll m){
	x %= m;
	ll ret = 1;
    while(n){
        if(n & 1LL) ret = modmult(ret, x, m);
        x = modmult(x, x, m);
        n >>= 1;
    }
    return ret;
}

ll SPRP[7] = {2LL, 325LL, 9375LL, 28178LL, 450775LL, 9780504LL, 1795265022LL};
bool RabinMiller(ll p, int t = 7)		//t = 7 for SPRP base
{
    if(p < 4) return (p > 1);
    if(!(p & 1LL)) return false;

    ll x = p - 1;
    int e = __builtin_ctzll(x);
    x >>= e;

    while(t--)
    {
//        ll witness = (rng() % (p-3)) + 2;	//Using random witness
        ll witness = SPRP[t];			//Using SPRP
        witness = modexpo(witness, x, p);
        if(witness <= 1) continue;

        for(int i = 0; i<e && witness != p-1; i++)
            witness = modmult(witness, witness, p);

        if(witness != p-1) return false;
    }
    return true;
}
//999999999999999989 [checker, it's a prime, ll(1e18)-11]

ll getPow(ll x){
    if(RabinMiller(x)) return x;
    ll y = (ll)sqrtl(x);
    if(y*y == x && RabinMiller(y)) return y;

    if(allpow.count(x)) return allpow[x];

    return -1;
}

int main(){
    FASTIO;

    precal();

    int n, k;
    cin>>n>>k;

    map<ll, vector<ll>> pows;
    vector<ll> candidates;

    ll best = -1;
    int bestcnt = 1e9;

    for(int i = 0; i<n; i++){
        ll x;
        cin>>x;

        ll p = getPow(x);
        if(p == -1 || pows[p].size() > 1){
            candidates.push_back(x);
        }
        else{
            pows[p].push_back(x);
        }
    }

    vector<ll> powdoubles;
    vector<ll> primes;

    for(auto &p : pows){
        if(p.second.size() <= 1) continue;
        primes.push_back(p.first);

        powdoubles.push_back(p.second[0]);
        powdoubles.push_back(p.second[1]);
    }

    for(int i = 0; i<candidates.size(); i++){
        ll tmp = candidates[i];

        int tmpcnt = 0;
        for(ll p : primes){
            if(tmp % p == 0) tmpcnt++;

            while(tmp % p == 0) tmp /= p;
            if(tmp == 1) break;
        }

        if(tmp > 1){
            candidates.erase(candidates.begin() + i);
            i--;
            continue;
        }

        if(tmpcnt < bestcnt){
            bestcnt = tmpcnt;
            best = candidates[i];
        }
    }

//    debug(), dbg(candidates);
//    debug(), dbg(powdoubles);
//    debug(), dbg(best), dbg(bestcnt);

    if(k == 1 || k > candidates.size() + powdoubles.size()){
        cout<<0<<endl;
        return 0;
    }

    if(k > powdoubles.size()){
        for(ll x : powdoubles){
            cout<<x<<" ";
            k--;
        }
        for(int i = 0; k>0; k--, i++){
            cout<<candidates[i]<<" ";
        }
        cout<<endl;
    }
    else if(k % 2 == 0){
        for(int i = 0; k>0; k--, i++)
            cout<<powdoubles[i]<<" ";
        cout<<endl;
    }
    else if(best == -1){
        cout<<0<<endl;
    }
    else if(1+2*bestcnt > k){
        cout<<0<<endl;
    }
    else {
        cout<<best<<" ";
        candidates.erase(find(candidates.begin(), candidates.end(), best));
        for(int i = 0; i<powdoubles.size(); i++){
            ll p = getPow(powdoubles[i]);
            if(best % p == 0){
                cout<<powdoubles[i]<<" ";
                powdoubles.erase(powdoubles.begin()+i);
                i--;
            }
        }
        k -= 1+2*bestcnt;
        for(int i = 0; k > 0; i++, k--){
            cout<<powdoubles[i]<<" ";
        }
        cout<<endl;
    }



    return 0;
}