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>
using namespace std;
#define int long long
#define N 1005
#define M 40000
int read(){
	int w=0,f=1;
	char c=' ';
	while(c<'0'||c>'9')c=getchar(),f=c=='-'?-1:f;
	while(c>='0'&&c<='9')w=w*10+c-48,c=getchar();
	return w*f;
}
namespace MR{
	const int p[13]={2,3,5,7,13,17,23,29,61,97,2333,4567,24251};
	mt19937_64 rnd(0); 
	int rad(int x){
	    return rnd()%x;
	}
	int mul(int a,int b,int mod){
	    int d=((long double)a/mod*b+0.5);
	    int r=a*b-d*mod;
	    return r<0?r+mod:r;
	}
	int expown(int x,int y,int mod){
		int res=1;
		x%=mod;
		while(y){
			if(y&1)res=mul(res,x,mod);
			x=mul(x,x,mod),y>>=1;
		}
		return res;
	}
	bool mr(int x){
		if(x<11)return x==p[0]||x==p[1]||x==p[2]||x==p[3];
		if(x<121){
			for(int i=0;i<4;i++)
				if(x%p[i]==0)return 0;
			return 1;
		}
		for(int i=0;i<13;i++){
			if(p[i]>=x)continue;
			if(expown(p[i],x,x)!=p[i])return 0;
		}
		int X=0,Y=x-1;
		while(!(Y&1))X++,Y>>=1;
		for(int i=0;i<3;i++){
			int r=rnd()%(x-2)+2,t=expown(r,Y,x);
			for(int j=0;j<X;j++){
				int k=mul(t,t,x);
				if(k==1&&t!=1&&t!=x-1)return 0;
				t=k;
			}
			if(t!=1)return 0;
		}
		return 1;
	}
}
const int inf=1e18;
int n,k,a[N],pri[M],cnt,p[N],t[N],ans[N],at,del[N],dt;
bool vis[M],fl[N];
vector<int>v[N];
void init(){
	for(int i=2;i<M;i++)
		if(!vis[i]){
			pri[++cnt]=i;
			for(int j=2;i*j<M;j++)
				vis[i*j]=1;
		}
}
int sq(int x,int y){
	int l=1,r=pow(1e18,1./y)+5,res=1;
	while(l<=r){
		int mid=(l+r)>>1,w=1;
		for(int i=1;i<=y;i++)
			w*=mid;
		if(w<=x)res=mid,l=mid+1;
		else r=mid-1;
	}
	return res;
}
int check(int x){
	for(int i=1;i<=cnt;i++)
		if(!(x%pri[i])){
			while(!(x%pri[i]))x/=pri[i];
			return x==1?pri[i]:0;
		}
	for(int i=1;i<=3;i++){
		int y=sq(x,i),w=1;
		for(int j=1;j<=i;j++)
			w*=y;
		if(w==x&&MR::mr(y))return y;
	}
	return 0;
}
unordered_map<int,int>mp;
signed main(){
	init();
	n=read(),k=read();
	if(k==1)return puts("0"),0;
	int tot=0,fw=0;
	bool flag=0;
	for(int i=1;i<=n;i++){
		a[i]=read(),p[i]=check(a[i]);
		if(p[i]){
			mp[p[i]]++;
			if(mp[p[i]]>=3)flag=1,fw=p[i];
		}
	}
	for(auto i:mp)
		if(i.second>=2)tot+=i.second;
		else del[++dt]=i.first;
	for(int i=1;i<=dt;i++)
		mp.erase(del[i]);
	for(int i=1;i<=n;i++){
		if(p[i])continue;
		int x=a[i];
		for(int j=1;j<=n;j++){
			if(!p[j]||mp[p[j]]<2)continue;
			if(!(x%p[j])){
				t[i]++,v[i].push_back(p[j]);
				while(!(x%p[j]))x/=p[j];
			}
		}
		if(x==1)fl[i]=1;
	}
	int minn=n+1,minid=0;
	for(int i=1;i<=n;i++)
		if(fl[i]&&t[i]<minn)minn=t[i],minid=i;
	if(k<tot){
		if(flag){
			for(auto i:mp){
				if(i.first==fw)continue;
				if(k<=3)break;
				for(int j=1;j<=i.second&&k-1>=2;j++)
					ans[++at]=i.first,k--;
			}
			for(int i=1;i<=k;i++)
				ans[++at]=fw;
		}
		else{
			if(k&1){
				if(k<minn*2+1)return puts("0"),0;
				for(auto i:v[minid])
					ans[++at]=i,ans[++at]=i,k-=2;
				ans[++at]=inf+a[minid],k--;
				for(auto i:mp)
					if(a[minid]%i.first)
						for(int j=1;j<=i.second&&k;j++)
							ans[++at]=i.first,k--;
			}
			else{
				for(auto i:mp)
					for(int j=1;j<=i.second&&k;j++)
						ans[++at]=i.first,k--;
			}
		}
	}
	else{
		for(auto i:mp)
			for(int j=1;j<=i.second;j++)
				ans[++at]=i.first,k--;
		for(int i=1;i<=n&&k;i++)
			if(fl[i])ans[++at]=inf+a[i],k--;
		if(k)return puts("0"),0;
	}
	for(int i=1;i<=at;i++){
		if(ans[i]>=inf)continue;
		for(int j=1;j<=n;j++)
			if(p[j]==ans[i]){
				p[j]=0,ans[i]=inf+a[j];
				break;
			}
	}
	for(int i=1;i<=at;i++)
		printf("%lld%c",ans[i]-inf,i==at?'\n':' ');
	return 0;
}