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;
  
#define int long long 
#define pb push_back
#define S second
#define F first
#define f(i,n) for(int i=0;i<n;i++)
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define vi vector<int>
#define pii pair<int,int>
#define all(x) x.begin(),x.end()

using u64 = uint64_t;
using u128 = __uint128_t;

u64 binpower(u64 base, u64 e, u64 mod) {
    u64 result = 1;
    base %= mod;
    
    while (e) {
        if (e & 1)
            result = (u128)result * base % mod;
        base = (u128)base * base % mod;
        e >>= 1;
    }
    
    return result;
}

bool check_composite(u64 n, u64 a, u64 d, int s) {
    u64 x = binpower(a, d, n);
    
    if (x == 1 || x == n - 1)
        return false;
    for (int r = 1; r < s; r++) {
        x = (u128)x * x % n;
        if (x == n - 1)
            return false;
    }
    
    return true;
}

bool MillerRabin(u64 n) { // returns true if n is prime, else returns false.
    if (n < 2)
        return false;

    int r = 0;
    u64 d = n - 1;
    while ((d & 1) == 0) {
        d >>= 1;
        r++;
    }
    
    for (int a : {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37}) {
        if (n == a)
            return true;
        if (check_composite(n, a, d, r))
            return false;
    }
    
    return true;
}

set<int> primes;

//maximum integers x so that x^i <= 10^18 
int lim[61] = {0,1000000000000000000,1000000000,1000000,31623,3982,1000,373,178,100,67,46,33,25,20,16,13,11,10,9,8,7,6,6,5,5,5,4,4,4,4,3,3,3,3,3,3,3,3,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2};

//return n^k , it is guaranteed to fit in the long long and n > 1
int pw(int n,int k)
{
    int res = 1;
    while(k--) res*=n;
    return res;
}

//return a number p s.t p^k = x and p is prime, if exists
int find(int x,int k)
{
    int l = 2;
    int r = lim[k];
    int res = -1;
    
    while(l <= r)
    {
        int mid = (l + r)/2;
        
        if(pw(mid,k) <= x)
        {
            res = mid;
            l = mid + 1;
        }
        else r = mid - 1;
    }
    
    if(pw(res,k) != x) return -1;
    
    if(!MillerRabin(res)) return -1;
    
    return res;
}

//Return a prime p if x = p^k
int primer(int x)
{
    int res = -1;
    
    for(int i=1;i<=60;i++)
    {
        res = find(x,i);
        if(res != -1) break;
    }
    
    return res;
}

//return -1 if x contains some other prime
//else return number of primes 

int make(int x)
{
    int cc = 0;
    
    for(auto v : primes)
    {
        if(x % v == 0)
        {
            cc++;   
            while(x % v == 0) x/=v;
        }
    }
    
    if(x != 1) return -1;
    return cc;
}

bool cmp(vector<int> & x1,vector<int> & x2)
{
    return (int)x1.size() > (int)x2.size();
}

signed main()
{
    fast;
    
    int n,k;
    cin >> n >> k;
    
    if(k == 1)
    {
        cout << 0;
        return 0;
    }
    
    map<int,vector<int> > pm;
   
    int x,y;
    
    f(i,n)
    {
       cin >> x;   
       pm[primer(x)].pb(x);
    }
    
    vector<vi> go;
    vector<pii> composite;
    
    for(auto x : pm)
    {
        if(x.F == -1) continue;
        
        if(x.S.size() > 1)
        {
            go.pb(x.S);
            primes.insert(x.F);
        }
    }
    
    for(auto  x : pm)
    {
        if(x.F == -1)
        {
            for(auto g : x.S)
            {
                int cc = make(g);
                if(cc != -1) composite.pb({cc,g});
            }
        }
    }
    
    //sort go by sizes
    sort(all(go),cmp);
    sort(all(composite));
    
    set<int> res;     
    int flag = 0;
    int last = -1;
    
    for(auto x : go)
    {
        for(auto y : x) 
        {
            if(res.size() < k)
            {
                if(y == x[0]) flag = 1;
                else flag = 0;
                
                res.insert(y);
                last = y;
            }
        }
    }
    
    //if the last prime we inserted was single then we try to fix    
    if(flag)
    {
        assert((int)res.size() == k);
        
        if(go.size() > 0 && go[0].size() > 2) 
        {
            //now we add the remaining prime and erase the first integer
            int gg = -1;
            
            for(auto x : go)
                for(auto y : x)
                  if(res.find(y) == res.end())
                    if(gg == -1) gg = y;
                
            res.insert(gg);
            res.erase(go[0][0]); 
        }
        else   
        {
            //first add a composite and then the primes according to it
            //and then some other primes 
            
            if(composite.size() == 0)
            {
                cout << 0;
                return 0;
            }
            
            res.clear();
            res.insert(composite[0].S);
            
            for(auto x : pm)
            {
                if(x.F == -1) continue;
                
                if(x.S.size() == 1) continue;
                
                if(composite[0].S % x.F != 0) continue;
                
                for(auto y : x.S) res.insert(y);
            }
            
            if(res.size() > k)
            {
                cout << 0;
                return 0;
            }
            
            for(auto x : go)
               for(auto y : x)
                 if(res.size() < k) res.insert(y);
        }
    }
    
    for(auto x : composite)
            if(res.size() < k) res.insert(x.second);
        
    if(res.size() < k) cout << 0;    
    else for(auto x : res) cout << x << ' ';   
}