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 M 1005
#define ll unsigned long long
int n,k,sk[]={2,3,5,7,11,13,17,19,23,29},mk[M],sl[M];
ll a[M],q[M];
ll Mul(ll a,ll b,ll p){
	return ((a*b-(ll)((long double)a*b/p+0.5)*p)+p)%p;
}
ll pw(ll x,ll p,ll P){
	ll ans=1;
	while(p){
		if(p&1)ans=Mul(ans,x,P);
		x=Mul(x,x,P);p>>=1;
	}return ans;
}
bool check(ll x){
	if(x==2)return 1;
	if(!(x&1))return 0;
	ll t=x-1;int cs=0;
	while(!(t&1))++cs,t>>=1;
	for(int i=0;i<10;++i){
		if((ll)sk[i]>=x)return (ll)sk[i]==x;
		ll tp=pw(sk[i],t,x);
		for(int j=1;j<=cs;++j){
			ll y=tp;tp=Mul(tp,tp,x);
			if(tp==1&&y!=1&&y!=x-1)return 0;
		}
		if(tp!=1)return 0;
	}
	return 1;
}
int sum[M],tot;
ll ls1[M];
void js(){
	puts("0");
	exit(0);
}
void sc(){
	for(int i=1;i<=n;++i){
		if(mk[i])printf("%llu ",a[i]);
		else if(q[i]&&sum[q[i]]){
			printf("%llu ",a[i]);
			--sum[q[i]];
		}
	}
}
int main(){
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;++i){
		scanf("%lld",&a[i]);
		for(int j=1;j<=60;++j){
			ll p=powl(a[i],1.0/j)+0.5;ll t=1;
			for(int k=1;k<=j;++k)if(t<=a[i]/p)t*=p;
			if(t==a[i]&&check(p)){
				q[i]=p;
				break;
			}
		}
	}for(int i=1;i<=n;++i)if(q[i])ls1[++tot]=q[i];
	sort(ls1+1,ls1+tot+1);tot=unique(ls1+1,ls1+tot+1)-ls1-1;
	for(int i=1;i<=n;++i)if(q[i])q[i]=lower_bound(ls1+1,ls1+tot+1,q[i])-ls1,sum[q[i]]++;
	
	for(int i=1;i<=n;++i){
		if(q[i]&&sum[q[i]]<2)q[i]=0;
		else if(q[i])q[i]=ls1[q[i]];
	}
	int zh=0,Tot=0;
	for(int i=1;i<=tot;++i)if(sum[i]>1)ls1[++Tot]=ls1[i],sum[Tot]=sum[i],zh+=sum[Tot];
	for(int i=1;i<=n;++i)if(q[i])q[i]=lower_bound(ls1+1,ls1+Tot+1,q[i])-ls1;
	tot=Tot;
	for(int i=1;i<=n;++i)if(!q[i]){
		ll tp=a[i];
		for(int j=1;j<=tot;++j){
			if(tp%ls1[j]==0)sl[i]++;
			while(tp%ls1[j]==0)tp/=ls1[j];
		}
		if(tp==1)zh++,mk[i]=1;
	}
	if(k>zh)js();
	if(k>=2*tot){
		for(int i=1;i<=n&&zh>k;++i)if(mk[i])mk[i]=0,zh--;
		for(int i=1;i<=tot&&zh>k;++i)while(zh>k&&sum[i]>2)sum[i]--,zh--;
		sc();
	}else{
		if(k==1)js();
		if(!(k&1)){
			for(int i=1;i<=n;++i)mk[i]=0;
			for(int i=1;i<=tot;++i)sum[i]=2;
			while(k<2*tot)sum[tot]=0,--tot;
		}else{
			int f=0;
			for(int i=1;i<=n;++i)if(mk[i]){
				if(f==0||sl[f]>sl[i])f=i;
				mk[i]=0;
			}
			if(f&&2*sl[f]+1<=k){
				mk[f]=1;
				for(int i=1;i<=tot;++i)sum[i]=2;
				zh=2*tot+1;
				for(int i=1;i<=tot&&zh>k;++i)if(a[f]%ls1[i])sum[i]=0,zh-=2;
			}else{
				f=0;
				for(int i=1;i<=tot;++i)if(sum[i]>2)f=i,sum[i]=2;
				if(!f)js();--k;zh=2*tot;
				for(int i=1;i<=tot&&zh>k;++i)if(i!=f)zh-=2,sum[i]=0;
				sum[f]++;
			}
		}sc();
	}
}
		 				 	     		  	 	  	  			