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>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;

const int M = 1000005;
const ll B = 1000000000000000005LL;

/******************* Miller Rabin starts *****************/

ll modit(ll x, ll mod) {
	if(x>=mod) x-=mod;
	return x;
}

/// Use __int128 if available
ll mult(ll x, ll y, ll mod) {
	ll s=0, m=x%mod;
	while(y) {
		if(y&1) s = modit(s+m, mod);
		y>>=1;
		m = modit(m+m, mod);
	}
	return s;
}

ll power(ll x, ll p, ll mod){
	ll s=1, m=x;
	while(p) {
		if(p&1) s = mult(s, m, mod);
		p>>=1;
		m = mult(m, m, mod);
	}
	return s;
}

bool witness(ll a, ll n, ll u, int t){
	ll x = power(a,u,n);
	for(int i=0; i<t; i++) {
		ll nx = mult(x, x, n);
		if (nx==1 && x!=1 && x!=n-1) return 1;
		x = nx;
	}
	return x!=1;
}

/**
    return 1 if prime, 0 otherwise
    Range : 10^18

    Magic bases:
    n < 4,759,123,141        3 :  2, 7, 61
    n < 1,122,004,669,633    4 :  2, 13, 23, 1662803
    n < 3,474,749,660,383    6 :  2, 3, 5, 7, 11, 13
    n < 2^64                 7 : 2, 325, 9375, 28178, 450775, 9780504, 1795265022
    Handles 40000 18 digit primes in 1 second on Toph
*/

vector<ll> bases = {2, 325, 9375, 28178, 450775, 9780504, 1795265022};
bool miller_rabin(ll n) {
	if (n < 2)    return 0;
	if (n%2==0)   return n==2;

	ll u = n-1;
	int t = 0;
	while(u%2==0)   u/=2, t++;  // n-1 = u*2^t

	for (ll v: bases) {
		ll a = v%(n-1) + 1;
		if(witness(a, n, u, t)) return 0;
	}
	return 1;
}

/******************* Miller Rabin ends *****************/

int n, k;
bool sv[M];

void sieve()
{
    sv[0] = sv[1] = true;

    for(int i = 4; i < M; i += 2) sv[i] = true;
    for(int i = 3; i*i < M; i += 2)
    {
        if(sv[i]) continue;

        for(int j = i*i; j < M; j += i+i) sv[j] = true;
    }
}

vector<pll> pprs;

void setup()
{
    sieve();

    for(int i = 2; i < M; i++)
    {
        if(sv[i]) continue;

        ll m = i;
        double d = i;

        while(d < 2*B)
        {
            pprs.push_back({m, i});
            m *= i, d *= i;
        }
    }

    sort(pprs.begin(), pprs.end());
}

ll ara[M];
ll basePr[M];
bool isImp[M];
vector<ll> validPrs;

bool getFactors(ll x, vector<ll>& vec)
{
    for(ll p: validPrs)
    {
        if(x%p == 0)
        {
            vec.push_back(p);
            while(x%p == 0) x /= p;
        }
    }

    return x == 1;
}

bool contains(const vector<ll>& vec, ll p)
{
    for(ll item: vec)
    {
        if(item == p) return true;
    }

    return false;
}

int ald;
vector<int> res;

void addIdx(int i)
{
    if(ald < k) ald++, res.push_back(i);
}

void addIdx(int i, int j)
{
    if(ald+1 < k) ald += 2, res.push_back(i), res.push_back(j);
}

int main()
{
    setup();

    scanf("%d %d", &n, &k);
    
    for(int i = 1; i <= n; i++) scanf("%lld", ara+i);

    for(int i = 1; i <= n; i++)
    {
        if(miller_rabin(ara[i]))
        {
            basePr[i] = ara[i];
            continue;
        }

        ll sq = sqrtl(ara[i]);
        if(sq*sq > ara[i]) sq--;
        if((sq+1)*(sq+1) <= ara[i]) sq++;

        if(sq*sq == ara[i] && miller_rabin(sq))
        {
            basePr[i] = sq;
            continue;
        }

        int j = lower_bound(pprs.begin(), pprs.end(), make_pair(ara[i], 0LL))-pprs.begin();
        assert(j < pprs.size());

        if(pprs[j].first == ara[i]) basePr[i] = pprs[j].second;
    }

    map<ll, vector<int>> ma;
    for(int i = 1; i <= n; i++)
    {
        if(basePr[i]) ma[basePr[i]].push_back(i);
    }

    for(pair<ll, vector<int>> p: ma)
    {
        if(p.second.size() >= 2)
        {
            validPrs.push_back(p.first);

            isImp[p.second[0]] = true;
            isImp[p.second[1]] = true;
        }
    }

    for(int i = 1; i <= n; i++)
    {
        if(isImp[i]) continue;

        vector<ll> vec;
        if(getFactors(ara[i], vec) && vec.size() <= k/2)
        {
            for(ll p: validPrs)
            {
                if(!contains(vec, p)) vec.push_back(p);
            }

            validPrs = vec;
            break;
        }
    }

    for(ll p: validPrs) addIdx(ma[p][0], ma[p][1]);
    for(int i = 1; i <= n; i++)
    {
        if(isImp[i]) continue;

        vector<ll> vec;
        if(getFactors(ara[i], vec) && vec.size() <= k/2) addIdx(i);
    }

    sort(res.begin(), res.end());

    if(res.size() < k) printf("0\n");
    else
    {
        for(int i: res) printf("%lld ", ara[i]);
        printf("\n");
    }
    
    return 0;
}
