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<set>
#include<map>
#include<stack>
#include<cmath>
#include<queue>
#include<cstdio>
#include<vector>
#include<climits>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define LL long long
#define int LL
using namespace std;
LL read(){
	bool f=0;LL x=0;char c=getchar();
	while(c<'0'||'9'<c){if(c=='-')f=1;c=getchar();}
	while('0'<=c&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
	return !f?x:-x;
}
const int MAXN=1000;
const LL INF=2e18+1;
LL Mul(LL x,LL y){
	if(x<=INF/y)
		x*=y;
	else x=INF;
	return x;
}
LL Pow(LL x,LL y){
	LL ret=1;
	while(y){
		if(y&1) ret=Mul(ret,x);
		x=Mul(x,x),y>>=1;
	}
	return ret;
}
vector<vector<int> > a;
map<LL,int>::iterator it;
LL Mul(LL x,LL y,LL Mod){
	LL ret=0;
	while(y){
		if(y&1) ret=(ret+x)%Mod;
		x=(x<<1)%Mod;
		y>>=1;
	}
	return ret;
}
LL Pow(LL x,LL y,LL Mod){
	LL ret=1;
	while(y){
		if(y&1) ret=Mul(ret,x,Mod)%Mod;
		x=Mul(x,x,Mod)%Mod;
		y>>=1;
	}
	return ret;
}
bool check(LL a,LL d,LL n){
	LL x=Pow(a,d,n);
	if(x==1||x==n-1)
		return true;
	while(d!=n-1){
		x=Mul(x,x,n),d<<=1;
		if(x==1) return false;
		if(x==n-1) return true;
	}
	return false;
}
int prime[15]={0,2,3,5,7,11,13,17,19,21,23,61,2333,4567,24251};
bool isprime(LL n){
	//if(n==2) return true;
	if(n<=1) return false;
	LL d=n-1;
	while((d&1)==0)
		d>>=1;
	for(int k=1;k<=14;k++){
		if(n==prime[k])
			return true;
		if(prime[k]<n&&check(prime[k],d,n)==false)
			return false;
	}
	return true;
}
map<LL,int> Id;
LL x[MAXN+5],p[MAXN+5];
vector<int> fc[MAXN+5];
signed main(){
	int n=read(),k=read(),cnt=0;
	for(int i=1;i<=n;i++){
		x[i]=read();
		for(int j=1;j<=60;j++){
			LL v=pow(x[i],1.0/j)-10;
			if(v<=0) v=1;
			while(1){
				LL tmp=x[i];
				bool fail=false;
				for(int k=1;k<=j;k++){
					if(tmp%v) fail=true;
					tmp/=v;
				}
				if(!tmp) break;
				if(!fail && tmp==1 && isprime(v)){
					break;
				}
				v++;
			}
			if(Pow(v,j)==x[i]&&isprime(v)){
				if(!Id.count(v))
					Id[v]=++cnt;
				a.resize(cnt+1);
				if(a[Id[v]].size()<2){
					a[Id[v]].push_back(i);
					p[i]=Id[v];
					goto Break;	
				}
			}
		}
		p[i]=-1;
		Break:;
	}
	for(int i=1;i<=n;i++){
		if(p[i]!=-1) continue;
		vector<int> q;
		LL v=x[i];
		for(it=Id.begin();it!=Id.end();it++){
			if(a[it->second].size()==1)//!!!!
				continue;
			if(v%it->first==0){
				while(v%it->first==0)
					v/=it->first;
				q.push_back(it->second);
			}
		}
		if(v==1)
			fc[i]=q;//°üº¬ËØÊý±àºÅ 
	}
	vector<LL> ans;
	if(k&1){
		int j=-1;//×î¶àÖÖËØÊý
		for(int i=1;i<=n;i++)
			if(!fc[i].empty()&&(j==-1||fc[i].size()<fc[j].size()))
				j=i;
		if(j==-1)
			puts("0"),exit(0);
		vector<bool> used(cnt+1);
		for(int i=0;i<(int)fc[j].size();i++)
			used[fc[j][i]]=1;
		ans.push_back(x[j]),k--;
		for(int i=1;i<=cnt;i++)
			if(used[i]){//a[i].size()=2
				ans.push_back(x[a[i][0]]);
				ans.push_back(x[a[i][1]]);
				k-=2;
			}
		if(k<0)
			puts("0"),exit(0);
		for(int i=1;i<=cnt;i++)
			if(!used[i]&&k&&a[i].size()==2){
				ans.push_back(x[a[i][0]]);
				ans.push_back(x[a[i][1]]);
				k-=2;
			}
		for(int i=1;i<=n;i++)
			if(!fc[i].empty()&&k&&i!=j)
				ans.push_back(x[i]),k--;
		if(k)
			puts("0"),exit(0);
	}
	else{
		for(int i=1;i<=cnt;i++){//ÎªÅ¼ÊýÓÅÏÈÁ½¸öÁ½¸ö·Å 
			if(k>0&&a[i].size()==2){
				ans.push_back(x[a[i][0]]);
				ans.push_back(x[a[i][1]]);
				k-=2;
			}
		}
		for(int i=1;i<=n;i++)
			if(!fc[i].empty()&&k)
				k--,ans.push_back(x[i]);
		if(k)
			puts("0"),exit(0);
	}
	for(int i=0;i<ans.size();i++)
		printf("%lld",ans[i]),putchar(i==ans.size()?'\n':' ');
	return 0;
}