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>
#define ll long long

//#define __int128 long long

using namespace std;

const int N = 1000+1;

ll ppow(__int128 x,ll y,ll mod)
{
    __int128 res=1;
    while(y)
    {
        if(y&1)
            res=res*x%mod;
        y>>=1;
        x=x*x%mod;
    }
    return res;
}

ll ppow(ll x,ll y)
{
    ll res=1;
    while(y)
    {
        if(y&1)
            res=res*x;
        y>>=1;
        x=x*x;
    }
    return res;
}

vector<ll> pr;

bool prime(ll x)
{
    for(ll p:pr)
        if(p*p>x)
            return true;
        else if(x%p==0)
            return false;
    for(ll _=0;_<100;_++)
    {
        ll a=rand()+1;
        if(ppow(a,x-1,x)!=1)
            return false;
    }
    return true;
}

ll check(ll x)
{
    for(ll i=1;i<=60;i++)
    {
        ll res=pow((long double)x,1/(long double)i);
        while(ppow(res,i)<x)
            res++;
        while(ppow(res,i)>x)
            res--;
        if(ppow(res,i)==x&&prime(res))
            return res;
    }
    return -1;
}

const ll CBRT=1e6+100;

ll lp[CBRT+1];

void init()
{
    for(ll i=2;i<=CBRT;i++)
    {
        if(lp[i]==0)
            lp[i]=i,pr.push_back(i);
        for(ll p:pr)
        {
            if(p>lp[i]||p*i>CBRT)
                break;
            lp[p*i]=p;
        }
    }
}

int n, k;
ll x[N];

bool cmp(const pair<vector<ll>, ll>& a, const pair<vector<ll>, ll>& b){
    return a.first.size() < b.first.size();
}

void fail(){
    cout << "0\n";
    exit(0);
}

int main(){
    ios_base::sync_with_stdio(false);
    cout.tie(0);
    cin.tie(0);
    init();
    cin >> n >> k;
    if(k==1)
        fail();
    set<ll> primes;
    map<ll, vector<ll>> mp;
    for(int i = 0; i < n; ++i){
        cin >> x[i];
        ll p = check(x[i]);
        if(p != -1){
            primes.insert(p);
            mp[p].push_back(x[i]);
        }
    }
    int cnt_primes = 0;
    bool only_pairs = true;
    for(auto el : mp){
        if(el.second.size() == 1){
            primes.erase(el.first);
            continue;
        }
        if(el.second.size() > 2)
            only_pairs = false;
        cnt_primes += el.second.size();
    }
    vector<pair<vector<ll>, ll>> other;
    for(int i = 0; i < n; ++i){
        vector<ll> d;
        ll num = x[i];
        for(ll p : primes)
            if(x[i] % p == 0){
                d.push_back(p);
                do x[i] /= p; while(x[i] % p == 0);
            }
        if(x[i] == 1 && d.size() > 1)
            other.emplace_back(d, num);
    }
    sort(other.begin(), other.end(), cmp);
    vector<ll> ans;
    if(cnt_primes < k){
        if(cnt_primes + other.size() < k)
            fail();
        for(ll p : primes)
            for(ll el : mp[p])
                ans.push_back(el);
        for(int i = 0; ans.size() < k; ++i)
            ans.push_back(other[i].second);
    }
    else if(only_pairs && k%2 == 1){
        if(other.empty() || 2*other[0].first.size() + 1 > k)
            fail();
        set<ll> used;
        ans.push_back(other[0].second);
        for(ll p : other[0].first){
            used.insert(p);
            ans.push_back(mp[p][0]);
            ans.push_back(mp[p][1]);
        }
        for(ll p : primes){
            if(ans.size() == k)
                break;
            if(used.find(p) != used.end())
                continue;
            ans.push_back(mp[p][0]);
            ans.push_back(mp[p][1]);
        }
    }
    else{
        for(ll p : primes){
            if(mp[p].size() == 2 && k-ans.size() == 2){
                ans.push_back(mp[p][0]);
                ans.push_back(mp[p][1]);
                continue;
            }
            if(k-ans.size() <= 3)
                break;
            if(mp[p].size() == 2){
                ans.push_back(mp[p][0]);
                ans.push_back(mp[p][1]);
            }
        }
        for(ll p : primes){
            if(mp[p].size() == 2)
                continue;
            if(k-ans.size() <= mp[p].size()){
                for(ll el : mp[p])
                    if(ans.size() < k)
                        ans.push_back(el);
            }
            else{
                for(ll el : mp[p])
                    if(ans.size() < k-2)
                        ans.push_back(el);
            }
        }
    }
    for(ll el : ans)
        cout << el << " ";
    cout << "\n";
}