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;

#define int long long
#define ll long long
#define ld long double
ll mul(ll a , ll b , ll p){ll c = a * b - (ll)((ld)a / p * b + 0.5) * p; return (c % p + p) % p;}
ll pw(ll a , ll b , ll p){ll t = 1; while(b){if(b & 1) t = mul(t , a , p); a = mul(a , a , p); b >>= 1;} return t;}

const int prmL[] = {2,3,5,7,11,13,17,19,23,29,31,37,24251,19260817} , sz = 14;
bool miller_rabin(ll x){
	for(int i = 0 ; i < sz ; ++i)
		if(x == prmL[i]) return 1; else if(x % prmL[i] == 0 || pw(prmL[i] , x - 1 , x) != 1) return 0;
	ll cur = x - 1; while(!(cur & 1)) cur >>= 1;
	for(int i = 0 ; i < sz ; ++i){
		ll val = pw(prmL[i] , cur , x); if(val == 1) continue;
		while(val != x - 1 && val != 1) val = mul(val , val , x);
		if(val == 1) return 0;
	}
	return 1;
}

ll gcd(ll p , ll q){while(q){ll r = p % q; p = q; q = r;} return p;}

mt19937 rnd(114514);
ll pollard_rho(ll p){
	ll c = rnd() % p + 1 , x0 = 0 , x = 0;
	for(int j = 1 ; ; j <<= 1 , x0 = x){
		ll tms = 1;
		for(int i = 1 ; i <= j ; ++i){
			x = (mul(x , x , p) + c) % p; tms = mul(tms , x - x0 + p , p);
			if(i % 128 == 0 && gcd(tms, p) != 1) return gcd(tms , p);
		}
		if(gcd(tms , p) != 1) return gcd(tms , p);
	}
}

vector < ll > prm;
void find(ll x){
	if(x == 1) return;
	if(miller_rabin(x)){prm.push_back(x); return;}
	ll t = x; while(t == x) t = pollard_rho(x);
	while(x % t == 0) x /= t;
	find(t); find(x);
}

vector < ll > p[1003]; map < ll , int > cnt; ll val[1003];

signed main(){
	int N , K; cin >> N >> K; int num = N; if(K == 1){puts("0"); return 0;}
	for(int i = 1 ; i <= N ; ++i){
		ll X; cin >> X; val[i] = X; find(X); sort(prm.begin() , prm.end());
		prm.resize(unique(prm.begin() , prm.end()) - prm.begin());
		p[i] = prm; if(prm.size() == 1) ++cnt[prm[0]];
		prm.clear();
	}
	auto pos = cnt.begin(); while(pos != cnt.end()) if(pos->second == 1) cnt.erase(pos++); else ++pos;
	for(int i = 1 ; i <= N ; ++i){
		bool flg = 1; for(auto t : p[i]) if(cnt.find(t) == cnt.end()) flg = 0;
		if(!flg){--num; p[i].clear();}
	}
	if(num < K) cout << 0;
	else{
		int sum = 0 , flg = 0; for(auto t : cnt){sum += t.second; if(t.second != 2) flg = t.first;}
		vector < ll > ans;
		if(sum <= K){
			for(int i = 1 ; i <= N ; ++i) if(p[i].size() == 1) ans.push_back(val[i]);
			for(int i = 1 ; i <= N && ans.size() < K ; ++i) if(p[i].size() > 1) ans.push_back(val[i]);
		}else if(flg || !(K & 1)){
			int lim = K; vector < ll > now , num; if(flg){now.push_back(flg); num.push_back(2); lim -= 2;}
			for(auto t : cnt) if(lim >= 2 && t.first != flg){now.push_back(t.first); num.push_back(min(lim , t.second)); lim -= min(lim , t.second);}
			num[0] += lim;
			for(int i = 1 ; i <= N ; ++i)
				if(p[i].size() == 1 && find(now.begin() , now.end() , p[i][0]) != now.end()){
					int t =find(now.begin() , now.end() , p[i][0]) - now.begin(); if(num[t]){--num[t]; ans.push_back(val[i]);}
				}
		}else{
			vector < ll > now , num; bool flg = 0;
			for(int i = 1 ; i <= N ; ++i)
				if(p[i].size() >= 2 && 2 * p[i].size() + 1 <= K){
					now = p[i]; ans.push_back(val[i]); num.resize(now.size() , 2);
					flg = 1; break;
				}
			if(!flg) ans.resize(1 , 0);
			else{
				for(auto t : cnt) if(K > 2 * now.size() + 1 && find(now.begin(),now.end() , t.first) == now.end()){
						now.push_back(t.first); num.push_back(2);
					}
				for(int i = 1 ; i <= N ; ++i)
					if(p[i].size() == 1 && find(now.begin() , now.end() , p[i][0]) != now.end()){
						int t =find(now.begin() , now.end() , p[i][0]) - now.begin(); if(num[t]){--num[t]; ans.push_back(val[i]);}
					}
			}
		}
		for(auto t : ans) cout << t << ' ';
		cout << endl;
	}
	return 0;
}