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 rep(i, a, b) for(int i = (a); i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
#define ff first
#define ss second
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef unsigned long long ull;
typedef long double ld;
const int S = int(3e5)+10;
const ll MOD = ll(1e9+7);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template <typename T>
void print(vector <T> &v) {
	trav(x, v)
		cout << x << " ";
	cout << endl;
}

ull mod_mul(ull a, ull b, ull M) {
	ll ret = a * b - M * ull(ld(a) * ld(b) / ld(M));
	return ret + M * (ret < 0) - M * (ret >= (ll)M);
}
ull mod_pow(ull b, ull e, ull mod) {
	ull ans = 1;
	for (; e; b = mod_mul(b, b, mod), e /= 2)
		if (e & 1) ans = mod_mul(ans, b, mod);
	return ans;
}

bool isPrime(ull n) {
	if (n < 2 || n % 6 % 4 != 1) return (n | 1) == 3;
	ull A[] = {2, 325, 9375, 28178, 450775, 9780504, 1795265022},
	    s = __builtin_ctzll(n-1), d = n >> s;
	trav(a, A) {   // ^ count trailing zeroes
		ull p = mod_pow(a%n, d, n), i = s;
		while (p != 1 && p != n - 1 && a % n && i--)
			p = mod_mul(p, p, n);
		if (p != n-1 && i != s) return 0;
	}
	return 1;
}

ull binpow(ull b, ull e) {
	ll ans = 1;
	for (; e; b = b * b, e /= 2)
		if (e & 1) ans = ans * b;
	return ans;
}

ull rt(ull n, int pw) {
	ull x = ull(pow(n, 1.0/pw));
	rep(i, -2, 3) {
		if(x+i > 0 && binpow(x+i, pw) == n)
			return x+i;
	}
	return 0;
}

bool ispw(ull x, ull n) {
	ull num = x;
	while(n/num >= x)
		num *= x;
	return (n == num);
}

int n, k;
ull a[1010], p[1010];
vi prs;


int main()
{
	//freopen("stuff.in", "r", stdin);
	cin.sync_with_stdio(0); cin.tie(0);
	cin >> n >> k;
	if(k == 1) {
		cout << "0\n";
		return 0;
	}
	rep(i, 0, n) 
		cin >> a[i];
	rep(i, 2, 1010) 
		if(isPrime(i))
			prs.push_back(i);
	
	rep(i, 0, n) {
		if(isPrime(a[i]))
			p[i] = a[i];
		else {
			rep(j, 2, 7) {
				ull r = rt(a[i], j);
				if(r && isPrime(r))
					p[i] = r;
			}
			if(!p[i]) {
				trav(pr, prs)
					if(ispw(pr, a[i])) {
						p[i] = pr;
						break;
					}
			}
		}
	}
	unordered_map<ull, int> m;
	unordered_map<ull, bool> pt;
	unordered_map<ull, vector<ull>> nums;
	vector <ull> res;

	rep(i, 0, n) {
		if(p[i]) {
			m[p[i]]++;
			nums[p[i]].push_back(i);
		}
	}
	int mx = 0;
	rep(i, 0, n)
		if(m[p[i]] == 1)
			p[i] = 0;
		else
			mx = max(mx, m[p[i]]);
	vi ps;
	rep(i, 0, n) {
		if(p[i] && !pt[p[i]]) {
			ps.push_back(p[i]);
			pt[p[i]] = true;
		}
	}
	if(mx > 2) {
		int mxx = 0;
		ull mxpr = 0;
		trav(pr, ps) {
			if(m[pr] > mxx) {
				mxx = m[pr];
				mxpr = pr;
			}
			if(sz(res) == k-1) {
				if(m[pr] > 2) {
					if(m[p[res.back()]] == 2) {
						res.pop_back();
						res.pop_back();
						rep(i, 0, 3)
							res.push_back(nums[pr][i]);
					} else {
						res.pop_back();
						rep(i, 0, 2)
							res.push_back(nums[pr][i]);
					}
				} else {
					if(mxx > 2) {
						rep(i, 0, sz(res))
							if(p[res[i]] == mxpr) {
								res.erase(res.begin() + i);
								break;
							}
						rep(i, 0, 2)
							res.push_back(nums[pr][i]);
					}
				}
			}
			else if(sz(res) + m[pr] > k) {
				int ssz = sz(res);
				rep(i, 0, k - ssz)
					res.push_back(nums[pr][i]);
			} else {
				rep(i, 0, m[pr])
					res.push_back(nums[pr][i]);
			}
			if(sz(res) == k)
				break;
		}
		if(sz(res) < k) {
			for(int i = 0; i < n && sz(res) < k; i++)
				if(!p[i]) {
					ull ai = a[i];
					trav(pr, ps) {
						while(ai % pr == 0)
							ai /= pr;
					}
					if(ai == 1)
						res.push_back(i);
				}
			if(sz(res) < k) {
				cout << "0\n";
				return 0;
			}
		}
	} else {
		int sm = 0;
		trav(pr, ps) {
			sm += m[pr];
		}
		if(k % 2 == 0 || sm < k) {
			trav(pr, ps) {
				if(sz(res) < k)
					rep(i, 0, m[pr])
						res.push_back(nums[pr][i]);
				if(sz(res) == k)
					break;
			}
			if(sz(res) < k) {
				for(int i = 0; i < n && sz(res) < k; i++)
					if(!p[i]) {
						ull ai = a[i];
						trav(pr, ps) {
							while(ai % pr == 0)
								ai /= pr;
						}
						if(ai == 1)
							res.push_back(i);
					}
				if(sz(res) < k) {
					cout << "0\n";	
					return 0;
				}
			}
		} else {
			rep(i, 0, n)
				if(!p[i]) {
					ull ai = a[i];
					int cnt = 0;
					trav(pr, ps) {
						if(ai % pr == 0)
							cnt++;
						while(ai % pr == 0)
							ai /= pr;
					}
					if(ai == 1 && cnt <= (k-1)/2) {
						int left = k - 1 - 2*cnt;
						res.push_back(i);
						trav(pr, ps) {
							if(a[i] % pr == 0) {
								rep(i, 0, m[pr])
									res.push_back(nums[pr][i]);
							} else if(left) {
								rep(i, 0, m[pr])
									res.push_back(nums[pr][i]);
								left -= 2;
							}
						}
					}
				}
		}
	}
	if(sz(res) < k)
		cout << "0\n";
	else {
		rep(i, 0, k)
			cout << a[res[i]] << " ";
		cout << endl;
	}
	
	return 0;
}