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:
/*Lucky_Glass*/
#include<map>
#include<cmath>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

typedef long long ll;
const int N=1e3+10;

int n,m,npk;
map<int,int> cnt;
pair<int,ll> pk[N];
bool ban[N];
int ndv[N],idx[N],ipk[N];
ll num[N],ans[N],dv[N][20];

namespace PRIME{
	const int B=1e5;
	int prm[B],nprm;
	bool vis[B+10];
	void Init(){
		for(int i=2;i<=B;i++){
			if(!vis[i]) prm[++nprm]=i;
			for(int j=1;j<=nprm && prm[j]*i<=B;j++){
				vis[prm[j]*i]=true;
				if(i%prm[j]==0) break;
			}
		}
	}
	inline ll Cube(int x){return 1ll*x*x*x;}
	inline ll Square(int x){return 1ll*x*x;}
	int Check(ll key,int le,int ri,ll Fun(int x)){
		while(le+1<ri){
			int mi=(le+ri)>>1;
			if(Fun(mi)<=key) le=mi;
			else ri=mi;
		}
		if(Fun(le)==key) return le;
		else if(Fun(ri)==key) return ri;
		return -1;
	}
	void ConfPk(int p,int id){
		cnt[p]++;
		ipk[id]=p;
	}
	bool Count(ll key,int id){
		bool fir=true;
		for(int i=1;i<=nprm;i++)
			if(key%prm[i]==0){
				dv[id][++ndv[id]]=prm[i];
				while(key%prm[i]==0) key/=prm[i];
				cnt[prm[i]]+=0;
				if(fir && key==1) ConfPk(prm[i],id);
				fir=false;
			}
		if(key>1){
			int tmp=Check(key,1,1e6,Cube);
			if(~tmp){
				dv[id][++ndv[id]]=tmp,cnt[tmp]+=0;
				if(fir) ConfPk(tmp,id);
				return false;
			}
			tmp=Check(key,1,1e9,Square);
			if(~tmp){
				dv[id][++ndv[id]]=tmp,cnt[tmp]+=0;
				if(fir) ConfPk(tmp,id);
				return false;
			}
			if(key<=1e9){
				dv[id][++ndv[id]]=key,cnt[key]+=0;
				if(fir) ConfPk(key,id);
				return false;
			}
			return true;
		}
		return false;
	}
};

void Ban(){
	for(int i=1;i<=n;i++)
		ban[i]=PRIME::Count(num[i],i);
	for(map<int,int>::iterator it=cnt.begin();it!=cnt.end();it++)
		if(it->second<=1){
			int p=it->first;
			for(int i=1;i<=n;i++)
				if(num[i]%p==0)
					ban[i]=true;
		}
	for(int i=1;i<=n;i++)
		if(ipk[i]>0 && !ban[i])
			pk[++npk]=make_pair(ipk[i],num[i]);
}
bool cmp(pair<int,ll> A,pair<int,ll> B){
	if(A.first!=B.first){
		if(cnt[A.first]!=cnt[B.first]) return cnt[A.first]>cnt[B.first];
		return A.first<B.first;
	}
	return A.second<B.second;
}
bool cmp2(int A,int B){
	if(cnt[A]!=cnt[B]) return cnt[A]>cnt[B];
	return A<B;
}
int main(){
	// freopen("input.in","r",stdin);
	PRIME::Init();
	scanf("%d%d",&n,&m);
	if(m==1){
		printf("0\n");
		return 0;
	}
	for(int i=1;i<=n;i++)
		scanf("%lld",&num[i]);
	Ban();
	int tcnt=0;
	for(int i=1;i<=n;i++)
		tcnt+=!ban[i];
	if(tcnt<m || !npk){
		printf("0\n");
		return 0;
	}
	if(npk<=m){
		bool fir=true;
		for(int i=1;i<=npk;i++){
			if(fir) fir=false;
			else putchar(' ');
			printf("%lld",pk[i].second);
		}
		for(int i=1,j=m-npk;i<=n && j;i++)
			if(!ban[i] && !ipk[i]){
				j--;
				if(fir) fir=false;
				else putchar(' ');
				printf("%lld",num[i]);
			}
		printf("\n");
		return 0;
	}
	sort(pk+1,pk+1+npk,cmp);
	if(pk[m].first==pk[m-1].first){
		for(int i=1;i<=m;i++) printf("%lld%c",pk[i].second,i==m? '\n':' ');
		return 0;
	}
	for(int i=1;i<=m-2;i++)
		if(pk[i].first==pk[i+1].first && pk[i+1].first==pk[i+2].first){
			swap(pk[i],pk[m+1]);
			for(int j=1;j<=m;j++) printf("%lld%c",pk[j].second,j==m? '\n':' ');
			return 0;
		}
	for(int i=1;i<=n;i++)
		if(!ban[i] && ipk[i]==0){
			if(ndv[i]*2>m-1) continue;
			sort(dv[i]+1,dv[i]+1+ndv[i],cmp2);
			int rem=m-1-2*ndv[i],debug=ndv[i];
			printf("%lld",num[i]);
			for(int j=1,k=1;j<=npk;j++)
				if(pk[j].first==dv[i][k]){
					printf(" %lld %lld",pk[j].second,pk[j+1].second);
					j++,k++;
					debug--;
				}
				else if(rem){
					printf(" %lld %lld",pk[j].second,pk[j+1].second);
					rem-=2,j++;
				}
			if(debug){
				printf("??");
				for(int j=1;j<=ndv[i];j++) printf("! %lld -> %d\n",dv[i][j],cnt[dv[i][j]]);
			}
			printf("\n");
			return 0;
		}
	printf("0\n");
	return 0;
}