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;

typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef pair <int,int> Pii;
#define reg register
#define mp make_pair
#define pb push_back
#define Mod1(x) ((x>=P)&&(x-=P))
#define Mod2(x) ((x<0)&&(x+=P))
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)
template <class T> inline void cmin(T &a,T b){ ((a>b)&&(a=b)); }
template <class T> inline void cmax(T &a,T b){ ((a<b)&&(a=b)); }

char IO;
template <class T=int> T rd(){
	T s=0; int f=0;
	while(!isdigit(IO=getchar())) f|=IO=='-';
	do s=(s<<1)+(s<<3)+(IO^'0');
	while(isdigit(IO=getchar()));
	return f?-s:s;
}

const int N=1e6+10;

int n,m;

int pri[N],pc,notpri[N];

ll qmul(ll x,ll y,ll P){
	ull z=(long double)x/P*y+0.5;
	ll res=(ull)x*y-z*P; 
	Mod2(res);
	return res;
}
ll qpow(ll x,ll k,ll P){
	ll res=1;
	for(;k;k>>=1,x=qmul(x,x,P)) if(k&1) res=qmul(res,x,P);
	return res;
}

int Miller_Rabin(ll n){
	if(n<N) return !notpri[n];
	if(~n&1) return 0;
	ll s=n-1,t=0;
	while(s%2==0) s/=2,t++;
	rep(k,1,7) {
		ll a=qpow(pri[rand()%pc+1],s,n),b;
		rep(i,1,t) {
			b=qmul(a,a,n);
			if(b==1 && a!=1 && a!=n-1) return 0;
			a=b;
		}
		if(a!=1) return 0;
	}
	return 1;
}

ll gcd(ll a,ll b){ return b==0?a:gcd(b,a%b); }

ll a[N],mk[N];
vector <ll> fac,F[N];
void Rho(ll n){
	if(n==1) return;
	if(Miller_Rabin(n)) return fac.pb(n);
	if(n<1e8) {
		for(int i=1;1ll*pri[i]*pri[i]<=n;++i) if(n%pri[i]==0) {
			fac.pb(pri[i]);
			while(n%pri[i]==0) n/=pri[i];
		}
		if(n>1) fac.pb(n);
		return;
	}
	rep(i,1,100) if(n%pri[i]==0) return fac.pb(pri[i]),Rho(n/pri[i]);
	//cout<<n<<' '<<N<<endl;
	//if(n<1e8) for(ll i=2;1ll*i*i<=n;++i) if(n%i==0) cerr<<"NOTPRIME!"<<endl;
	ll x=1ll*rand()*rand()%n,y=x,c=1ll*rand()*rand()%n;
	do {
		x=qmul(x,x,n)+c,x>=n&&(x-=n);
		y=qmul(y,y,n)+c,y>=n&&(y-=n);
		y=qmul(y,y,n)+c,y>=n&&(y-=n);
	} while(gcd(abs(x-y),n)==1);
	ll g=gcd(abs(x-y),n);
	//cout<<"$"<<x<<' '<<y<<' '<<g<<endl;
	return Rho(g),Rho(n/g);
}

map <ll,vector<int> > M;
ll ans[N];
void Outp(){
	rep(i,1,m) ans[i]=a[ans[i]];
	sort(ans+1,ans+m+1);
	rep(i,1,m) printf("%lld ",ans[i]);
	exit(0);
}

int main(){
	srand(time(NULL));
	//freopen("test.in","r",stdin);
	rep(i,2,N-1) if(!notpri[i]) {
		pri[++pc]=i;
		for(int j=i+i;j<N;j+=i) notpri[j]=1;
	}
	n=rd(),m=rd();
	rep(i,1,n) a[i]=rd<ll>();
	rep(i,1,n) {
		fac.clear();
		ll x=a[i];
		//cout<<"$"<<i<<endl;
		rep(j,1,n) {
			ll g=gcd(x,a[j]);
			//cout<<"$"<<i<<' '<<j<<' '<<g<<endl;
			if(g==1 || g==x || g==0) continue;
			if(g>x/g) g=x/g;
			//puts("!"),cout<<g<<endl;
			Rho(g);
			while(1) {
				ll t=gcd(x,g);
				if(t==1) break;
				x/=t;
			}
			//puts("!!");
		}
		//puts("!");
		for(ll i:fac) while(x%i==0) x/=i;
		if(x>1) {
			//puts("!!");
			if(Miller_Rabin(x)) fac.pb(x);
			else {
				//puts("!!!");
				//cout<<x<<endl;
				for(int i=1;1ll*pri[i]*pri[i]*pri[i]<=x && i<=pc;++i) if(x%pri[i]==0) {
					while(x%pri[i]==0) x/=pri[i];
					fac.pb(pri[i]);
				}
				if(!Miller_Rabin(x)){ 
					ll g=round(sqrt(x));
					if(g*g>x) g--;
					if(g*g>x) g--;
					if((g+1)*(g+1)<=x) g++;
					if(g*g==x) fac.pb(g);
					else fac.pb(-1),fac.pb(-2);
				} else if(x>1) fac.pb(x);
			}
		}
		//if(clock()>1.9*CLOCKS_PER_SEC) return printf("%d\n",i),puts("0"),0;
		F[i]=fac;
		sort(F[i].begin(),F[i].end()),F[i].erase(unique(F[i].begin(),F[i].end()),F[i].end());
		//printf("#%5lld  :: ",a[i]);  
		//for(ll j:F[i]) cout<<j<<' ';
		//puts("");
		if(F[i].size()==1 && M[F[i][0]].size()<2) M[F[i][0]].pb(i),mk[i]=1;
	}
	int c=0;
	for(auto i:M) if(i.second.size()>=2) c++;
	if(m%2==0 && c*2>=m) {
		//puts("TYPE#1#");
		int k=m;
		for(auto i:M) if(i.second.size()>=2) {
			if(!k) break;
			rep(j,0,1) ans[k--]=i.second[j];
		}
		Outp();
	}
	if(c*2>=m) {
		//puts("TYPE#2#");
		rep(i,1,n) if(!mk[i] && (int)F[i].size()<=m/2) {
			int f=1;
			for(ll x:F[i]) if(M[x].size()<2) f=0;
			//cout<<"$"<<i<<' '<<f<<endl;
			if(f) {
				int k=m;
				ans[k--]=i;
				for(ll x:F[i]) {
					rep(j,0,1) ans[k--]=M[x][j];
					M.erase(x);
				}
				for(auto i:M) if(i.second.size()>=2) {
					if(!k) break;
					rep(j,0,1) ans[k--]=i.second[j];
				}
				Outp();
			}
		}
	} else {
		//puts("TYPE#3#");
		int k=m;
		for(auto i:M) if(i.second.size()>=2) {
			if(!k) break;
			rep(j,0,1) ans[k--]=i.second[j];
		}
		rep(i,1,n) if(!mk[i]) {
			if(!k) break;
			int f=1;
			for(ll x:F[i]) if(M[x].size()<2) f=0;
			if(f) ans[k--]=i;
		}
		if(!k) Outp();
	}
	puts("0");
}