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 forr(i,a,b) for(int i=(a);i<(b);i++)
#define forn(i,n) forr(i,0,n)
#define dforn(i,n) for(int i=n-1;i>=0;i--)
#define forall(it,v) for(auto it=v.begin();it!=v.end();it++)
#define sz(c) ((int)c.size())
#define rsz resize
#define pb push_back
#define mp make_pair
#define lb lower_bound 
#define ub upper_bound
#define fst first
#define snd second

#ifdef ANARAP
#else
#endif

using namespace std;

typedef long long ll;
typedef pair<int,int> ii;

ll mulMod(ll a, ll b, ll m){
	ll x=0, y=a%m;
	while(b>0){
		if(b%2==1) x=(x+y)%m;
		y=(y*2)%m;
		b/=2;
	}
	return x%m;
}

ll expMod(ll b, ll e, ll m){
	if(!e) return 1;
	ll q= expMod(b,e/2, m);
	q=mulMod(q,q,m);
	return e%2? mulMod(b,q,m) : q;
	
}



bool es_primo_prob(ll n,int a){
	if(n==a) return true;
	ll s=0, d=n-1;
	while(d%2==0) s++, d/=2;
	ll x=expMod(a,d,n);
	if((x==1)||(x+1==n)) return true;
	forn(i,s-1){
		x=mulMod(x,x,n);
		if(x==1) return false;
		if(x+1==n) return true;
		
	}
	return false;
}

map<ll, bool> dprabin;

bool rabin(ll n){
	if(n==1) return false;
	if(dprabin.count(n)) return dprabin[n];
	const int ar[]={2,3,5,7,11,13,17,19,23};
	forn(j,9) if(!es_primo_prob(n,ar[j])) return dprabin[n] = false;
	return dprabin[n] = true;
}

ll getPrimeBase(ll x)
{
	if(rabin(x)) return x;
	forr(e,2,65)
	{
		__int128 L = 2, R = sqrt(x)+2, M;
		while(L < R)
		{
			M = (L+R)/2;
			__int128 aux = 1;
			forn(i,e)
			{
				aux *= M;
				if(aux > x) break;
			}
			if(aux == x) L = R = M;
			else if(aux < x) L = M+1;
			else R = M-1;
		}
		if(L == R)
		{
			__int128 aux = 1;
			forn(i,e) aux *= L;
			if(aux == x && rabin(L)) return L;
		}
	}
	return -1;
}

set<ll> goodPrimes;

bool fact2(ll n, map<ll,ll> &f)
{
	assert(n > 1);
	forall(it, goodPrimes)
	{
		while(n%*it == 0)
		{
			n /= *it;
			f[*it]++;
		}
		if(n == 1) return true;
	}
	return false;
}

int main()
{
	
	#ifdef ANARAP
		freopen("input.in", "r", stdin);
		//freopen("output.out", "w", stdout);
	#endif
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	ll n,k;
	cin >> n >> k;
	if(k == 1)
	{
		cout << "0\n";
		return 0;
	}
	vector<ll> v(n);
	vector<bool> isPot(n, false);
	map<ll, vector<int>> m;
	forn(i,n)
	{
		cin >> v[i];
		ll p = getPrimeBase(v[i]);
		if(p != -1)
		{
			m[p].pb(i);
			isPot[i] = true;
			//cout << v[i] << ' ' << p << '\n';
		}
	}
	ll sum = 0;
	forall(it, m) if(sz(it->snd) >= 2)
	{
		goodPrimes.insert(it->fst);
		sum += sz(it->snd);
	}
	if(k%2 == 0 && 2*sz(goodPrimes) >= k)
	{
		forall(it,m) if(sz(it->snd) >= 2)
		{
			if(k == 0) break;
			cout << v[it->snd[0]] << ' ' << v[it->snd[1]] << ' ';
			k -= 2;
		}
		return 0;
	}
	assert(sum >= 2*sz(goodPrimes));	
	if(sum >= k && sum > 2*sz(goodPrimes))
	{
		vector<ll> ans;
		ll bigPrime = -1, auxsz = 0;
		forall(it,m) if(sz(it->snd) >= 2)
		{
			if(auxsz < sz(it->snd)) auxsz = sz(it->snd), bigPrime = it->fst;
		}
		assert(bigPrime != -1);
		assert(auxsz > 2);
		forn(i,min(auxsz, k)) ans.pb(v[m[bigPrime][i]]);
		k -= min(auxsz, k);
		bool needBad = false;
		forall(it,m) if(sz(it->snd) >= 2 && it->fst != bigPrime)
		{
			if(k == 0) break;
			if(k == 1) needBad = true, k++;
			forn(i, sz(it->snd))
			{
				if(k == 0) break;
				ans.pb(v[it->snd[i]]);
				k--;
			}
		}
		if(needBad)
		{
			forr(i,1,sz(ans)) cout << ans[i] << ' ';
		}
		else
		{
			forn(i,sz(ans)) cout << ans[i] << ' ';
		}
		cout << '\n';
		return 0;
	}
	if(sz(goodPrimes) < 2)
	{
		cout << "0\n";
		return 0;
	}
	vector<map<ll,ll>> vf(n);
	int auxcant = 0;
	vector<bool> good(n, false);
	forn(i,n) if(!isPot[i] && fact2(v[i], vf[i]))
	{
		if(sum < k) assert(2*sz(vf[i]) < k);
		if(2*sz(vf[i]) + 1 > k) vf[i].clear();
		else
		{
			auxcant++;
			good[i] = true;
			if(sum >= k)
			{
				assert(k%2);
				assert(sum == 2*sz(goodPrimes));
				k--;
				cout << v[i] << ' ';
				set<ll> usedPrimes;
				forall(it,vf[i])
				{
					k -= 2;
					cout << v[m[it->fst][0]] << ' ' << v[m[it->fst][1]] << ' ';
					usedPrimes.insert(it->fst);
				}
				assert(k >= 0);
				forall(it,m) if(sz(it->snd) >= 2 && !usedPrimes.count(it->fst))
				{
					if(k == 0) break;
					cout << v[it->snd[0]] << ' ' << v[it->snd[1]] << ' ';
					k -= 2;
				}
				assert(k == 0);
				return 0;
			}
		}
	}
	if(sum < k && sum+auxcant >= k)
	{
		set<int> ans;
		int aux = 0;
		forall(it,m) if(sz(it->snd) >= 2)
		{
			forn(i, sz(it->snd))
			{
				ans.insert(it->snd[i]);
				aux++;
			}
		}
		assert(aux == sum);
		k -= sum;
		assert(k > 0);
		forn(i,n) if(good[i])
		{
			if(k == 0) break;
			ans.insert(i);
			k--;
		}
		assert(k == 0);
		forall(it, ans) cout << v[*it] << ' ';
		cout << '\n';
	}
	else cout << "0\n";
	return 0;
}