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 
#include <bits/stdc++.h>
#define loop(i, a, b) for(long long i=a;i<b;i++)
#define pool(i, a, b) for(long long i=a-1;i>=b;i--)
#define fore(i, a) for(auto&& i:a)
#define fi first
#define se second
#define ps(a) push_back(a)
#define pb(a) pop_back(a)
#define sc scanf
#define vc vector
#define pa pair<ll, ll>
#define ll long long
#define lb lower_bound
#define ub upper_bound
#define all(a) a.begin(), a.end()
#define llmax LLONG_MAX/2
#define llmin -LLONG_MAX/2
using namespace std;
#define mn 1010
#define pa pair<ll, ll>
#define ld long double
#define mod 1000000007
ll arr[mn];
ll getrid(ll m, ll p){
    while(m%p==0) m/=p;
    return m;
}
ll potgcd(ll a, ll b){
    if(a<b) swap(a, b);
    if(a%b!=0) return llmax;
    return (b) ? b:potgcd(b, getrid(a, b));
}
const ll siv=100000;
ll isp[siv];
vc<ll> p;
ll ispp(ll prima){
    fore(v, p){
        ll que=getrid(prima, v);
        if(que==1) return v;
        if(que!=prima) return 0;
    }
    return prima;
}
map<ll, vc<ll>> pot;
ll br[mn];
int main() {
    ll n, k;cin >> n >> k;
    loop(i, 0, n)cin >> arr[i];
    if(k==1){
        cout << 0<<endl;
        return 0;
    }
    loop(i, 2, siv) if(!isp[i]){ p.ps(i); for(ll j=i * i;j<siv; j+=i) isp[j]=1;}
    loop(i, 0, n){
        ll mm=llmax;
        loop(j, 0, i){
            ll que=potgcd(arr[i], arr[j]);
            mm=min(mm, que);
        }
        ll que =ispp(mm);
        if(que) pot[que];
    }
    loop(i, 0, n) fore(v, pot) if(getrid(arr[i], v.fi)==1) v.se.ps(i);
    
    vc<ll> tre;fore(v, pot) if((ll)v.se.size() <2) tre.ps(v.fi);
    fore(v, tre) pot.erase(v);
    
    
    ll msiz=0, cnt=0;
    
    fore(v, pot) msiz=max(msiz, (ll)v.se.size()), cnt+=v.se.size();
    fore(v, pot) fore(u, v.se) br[u]=1;
    vc<ll> ans;

    if(msiz==2 and k%2){
 
            ll konc=0;
            loop(i, 0, n) if(!br[i]){
                ll car=arr[i];
                vc<ll> del;
                fore(v, pot){
                    ll que=getrid(car, v.fi);
                    if(que!=car) car=que, del.ps(v.fi);
                }
                if(car==1 and del.size()<=(k-1)/2){
                    ans.ps(arr[i]);
                    fore(v, del) fore(u, pot[v]) ans.ps(arr[u]);
                    fore(v, del) pot.erase(v);
                    
                    fore(v, pot) if(ans.size()<k) fore(u, v.se) ans.ps(arr[u]);
                    if(ans.size()==k){fore(v, ans) cout << v << " ";konc=1;}
                }
            }
            if(!konc) cout << 0<<endl;
    }
    else{
        if (msiz==0) cout << 0<<endl;
        else if(cnt>=k){
            if(msiz==2){
                fore(v, pot) if(ans.size()<k){fore(u, v.se) ans.ps(arr[u]);}
                fore(v, ans) cout << v << " ";
            }
            else{
                fore(v, pot) if(v.se.size()>2){
                    fore(u, v.se) if(ans.size()<k) ans.ps(arr[u]) ;
                    pot.erase(v.fi);
                    break;
                }
                if(ans.size()<k){
                    fore(v, pot) if(ans.size()<k){
                        loop(i, 0, v.se.size()){
                            if(ans.size()==k and i==1) ans.ps(arr[v.se[i]]);
                            if(ans.size()<k) ans.ps(arr[v.se[i]]);
                            
                        }
                    }
                }
                if(ans.size()>k) ans.erase(ans.begin());
                fore(v, ans) cout << v << " ";
            }
        }
        else{
            fore(v, pot) fore(u, v.se) ans.ps(arr[u]);
            loop(i, 0, n) if(!br[i] and (ll)ans.size()<k){
                ll car=arr[i];
                fore(v, pot) car=getrid(car, v.fi);
                if(car==1) ans.ps(arr[i]);
            }
            if(ans.size()==k)fore(v, ans) cout << v << " ";
            else cout << 0 <<endl;
        }
    }
}