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:
#pragma GCC target ("avx2")
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>

using namespace std;
typedef long long int ll;
typedef long double ld;

typedef pair<ll, ll> pl;

#define all(a) (a).begin(), (a).end()
#define K first
#define V second
#define TC ll t;cin>>t;while(t--)

template<class T, class S>
ostream& operator<<(ostream &o, pair<T, S> p) {
    return o<<'('<<p.first<<", "<<p.second<<')';
}

template<template<class, class...> class T, class... A>
typename enable_if<!is_same<T<A...>, string>(), ostream&>::type
operator<<(ostream &o, T<A...> V) {
	o<<'[';
	for(auto a:V) o<<a<<", ";
	return o<<']';
}

template<ll i, class... T>
typename enable_if<i==sizeof...(T)>::type _p(ostream& o, tuple<T...> t) {}

template<ll i, class... T>
typename enable_if<i<sizeof...(T)>::type _p(ostream& o, tuple<T...> t) {
    _p<i+1>(o << get<i>(t)<< ", ", t);
}
 
template<class... T>
ostream& operator<<(ostream& o, tuple<T...> t) {
    _p<0>(o<<'(', t);
    return o<<')';
}

__int128 powmod(__int128 x, ll y){
  if(y==0) return 1;
  __int128 t=powmod(x,y/2);
  if (y%2==0) return (t*t);
  return (((x*t))*t);
}

namespace ml {
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 is_prime(ll n) {
    if (n < 2)
        return false;

    ll r = 0;
    ll d = n - 1;
    while ((d & 1) == 0) {
        d >>= 1;
        r++;
    }

    for (ll a : {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37}) {
        if (n == a)
            return true;
        if (ml::check_composite(n, a, d, r))
            return false;
    }
    return true;
}

ll perfect(ll n) {
	ll base;
	for (ll y=65; y>=1; --y) {
		ll x = llroundl(powl(n, 1.l/y));
		if (powmod(x, y)==n) {base=x; break;}
	}
	if (is_prime(base)) return base;
	return -1;
}

vector<ll> ret;

ll good(ll x, vector<ll> & prims) {
	ret.clear();
	for (auto p:prims) {
		if (x%p==0) {
			ret.push_back(p);
			while (x%p==0) x/=p;
		}
	}
	if (x!=1) return 0;
	return 1;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	ll n, k;
	cin>>n>>k;
	vector<ll> extra;
	map<ll, vector<ll>> base;
	for (ll i=0; i<n; ++i) {
		ll x;
		cin>>x;
		ll p = perfect(x);
		if (p==-1) extra.push_back(x);
		else {
			if (base[p].size()==2) extra.push_back(x);
			else base[p].push_back(x);
		}
	}
	vector<ll> todel;
	for (auto &a:base) {
		if (a.second.size()<2) todel.push_back(a.first);
	}
	for (auto o:todel) base.erase(o);

	vector<ll> prims;
	for (auto o:base) {
		prims.push_back(o.first);
	}
	if (base.size()*2 <k ) {
			vector<ll> ans;
			for (auto o:base) {
				for (auto u:o.second)ans.push_back(u);
			}
			k-=base.size()*2;
			for (auto x:extra) {
				if (k && good(x, prims)){ans.push_back(x); --k;}
			}
			if(k) cout<<0;
			else for (auto o:ans)cout<<o<<' ';
			cout<<'\n';
			return 0;
	}

	if (k%2) {
		pl best = {LLONG_MAX, -1};
		for (ll i=0; i<extra.size(); ++i) {
			ll x = extra[i];
			if (!good(x, prims)) continue;
			best = min(best, {ret.size(), x});
		}
		if (best.second==-1 || best.first>k/2) {
			cout<<0<<'\n';
			return 0;
		}
		cout<<best.second<<' ';
		--k;
		good(best.second, prims);
		for (auto o:ret) {
			for (auto u:base[o]) cout<<u<<' ';
			k-=2;
			base.erase(o);
		}
	}

	for (ll i=0; i<k/2; ++i) {
		for (auto u:base.begin()->second) cout<<u<<' ';
		base.erase(base.begin());
	}
	cout<<'\n';

}