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;

const int maxn = 1005;
const int maxm = 1e6+5;
typedef long long ll;
struct Node{
	int u,cnt;
	vector<ll> val;
	friend bool operator <(Node a,Node b){
		return a.cnt>b.cnt;
	}
};
struct Node2{
	int u;ll v;
	friend bool operator <(Node2 a,Node2 b){
		return a.u<b.u;
	}
};
vector<Node>group;
vector<ll>res;
int prim[maxm],tot=0;
bool flag[maxm];
void init(int n){
	for(int i=2;i<=n;++i){
		if(!flag[i])prim[tot++]=i;
		for(int j=0;j<tot && prim[j]*i<=n;++j){
			flag[i*prim[j]]=1;
			if(i%prim[j]==0)break;
		}
	}
}
bool is_prime(int x){
	if(x<maxm && !flag[x])return true;
	for(int i=0;i<tot && 1ll*prim[i]*prim[i]<=x;++i){
		if(x%prim[i]==0)return false;
	}
	return true;
}
int checkp2(ll x){
	int y=sqrtl(x);
	while(1ll*y*y<x)y++;
	while(1ll*y*y>x)y--;
	if(1ll*y*y!=x)return -1;
	if(is_prime(y))return y;
	return -1;
}
int checkp3(ll x){
	for(int i=0;i<tot && 1ll*prim[i]*prim[i]*prim[i]<=x;++i){
		if(x%prim[i]==0){
			while(x%prim[i]==0){
				x/=prim[i];
			}
			if(x==1)return prim[i];
			return -1;
		}
	}
	return -1;
}
vector<ll>lis,best;
ll bst=0;
bool findres(){
	for(auto u:res){
		ll ori=u;
		for(int i=0;i<group.size();++i){
			int v=group[i].u;
			if(u%v==0){
				while(u%v==0){
					u/=v;
				}
				lis.push_back(i);
			}
		}
		if(u==1 && (best.empty() || lis.size()<best.size()))best=lis,bst=ori;
		lis.clear();
	}
	return !best.empty();
}
void findres2(){
	for(auto u:res){
		ll ori=u;
		for(int i=0;i<group.size();++i){
			int v=group[i].u;
			if(u%v==0){
				while(u%v==0){
					u/=v;
				}
			}
		}
		if(u==1)lis.push_back(ori);
	}
}
int vis[maxn];
int main(){
	init(maxm-1);
	int n,k;
	scanf("%d%d",&n,&k);
	vector<Node2>lins;
	for(int i=1;i<=n;++i){
		ll u;
		scanf("%lld",&u);
		int p;if(u<=1e9 && is_prime(u))p=u;else p=checkp2(u);
		if(p==-1){
			p=checkp3(u);
			if(p==-1)res.push_back(u);else lins.push_back(Node2{p,u});
		}else lins.push_back(Node2{p,u});
	}
	if(k==1)return printf("0\n"),0;
	sort(lins.begin(),lins.end());
	for(int i=0;i<lins.size();++i){
		if(!i || lins[i].u!=lins[i-1].u){
			if(!group.empty() && group.back().cnt==1)group.pop_back();
			Node now;now.val.clear();
			now.u=lins[i].u,now.cnt=1,now.val.push_back(lins[i].v);
			group.push_back(now);
		}else group.back().cnt++,group.back().val.push_back(lins[i].v);
	}
	if(!group.empty() && group.back().cnt==1)group.pop_back();
	int sum=0;
	bool two=true;
	for(int i=0;i<group.size();++i){
		sum+=group[i].cnt;
		two&=(group[i].cnt==2);
	}
	if(sum>=k){
		if(two){
			if(k&1){
				if(!findres() || best.size()>(k-1)/2)return printf("0\n"),0;
				printf("%lld ",bst);
				for(int i=0;i<best.size();++i)printf("%lld %lld ",group[best[i]].val[0],group[best[i]].val[1]),vis[best[i]]=1;
				int ct=(k-1)/2-best.size();
				for(int i=0;i<group.size();++i){
					if(!ct)break;
					if(vis[i])continue;
					printf("%lld %lld ",group[i].val[0],group[i].val[1]);
					ct--;
				}
				puts("");
			}else{
				for(int i=0;i<k/2;++i){
					printf("%lld %lld ",group[i].val[0],group[i].val[1]);
				}puts("");
			}
		}else{
			deque<ll>as;
			sort(group.begin(),group.end());
			for(int i=0;i<group.size();++i){
				int d=k-as.size();
				if(d>=2){
					for(int j=0;j<min((int)group[i].val.size(),d);++j){
						as.push_back(group[i].val[j]);
					}
				}else if(!d)break;
				else {
					as.pop_front();
					for(int j=0;j<2;++j)as.push_back(group[i].val[j]);
				}
			}
			while(!as.empty()){
				ll u=as.front();as.pop_front();
				printf("%lld ",u);
			}puts("");
		}
	}else{
		findres2();
		vector<ll>as;
		for(int i=0;i<group.size();++i){
			for(int j=0;j<group[i].val.size();++j){
				as.push_back(group[i].val[j]);
			}
		}
		int d=k-as.size();
		while(d && !lis.empty()){
			as.push_back(lis.back());
			lis.pop_back();
			d--;
		}
		if(d)printf("0\n");
		else{
			for(int i=0;i<as.size();++i)printf("%lld ",as[i]);
			puts("");
		}
	}
}