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:
#pragma comment(linker, "/STACK:9759095000")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,abm,mmx,tune=native")
#include<vector>
#include<iostream>
#include<stack>
#include<cmath>
#include<algorithm>
#include<set>
#include<map>
#include<string>
#include<tuple>
#include<bitset>
#include<queue>
#include<unordered_map>
#include<random>
#include<ctime>
//#define double long double
typedef long long ll;
typedef double ld;
typedef unsigned long long ull;
using namespace std;
ll gcd(ll i, ll j) {
	if (j == 0)return i;
	else return gcd(j, i % j);
}
#ifdef _DEBUG
ll __builtin_popcount(ll x) { return x ? (__builtin_popcount(x >> 1) + (x & 1)) : 0; }
#endif
template<typename T> inline T getint() {
	T val = 0;
	char c;

	bool neg = false;
	while ((c = getchar()) && !(c >= '0' && c <= '9')) {
		neg |= c == '-';
	}

	do {
		val = (val * 10) + c - '0';
	} while ((c = getchar()) && (c >= '0' && c <= '9'));

	return val * (neg ? -1 : 1);
}
//#define int long long
const ll INF = 1e18;
const int mod = 1000000007, mod1 = 1000000009;
const ld eps = 1e-9, pi = acos(-1);
const int maxN = 1000100, maxT = 1601;
vector<ll>p;
int pr[maxN];
void build_prime() {
	for (int i = 2; i < maxN; ++i) {
		if (pr[i] == 0) {
			p.push_back(i);
			for (int j = 2 * i; j < maxN; j += i)pr[j] = 1;
		}
	}
}
bool is_it_prime(ll v) {
	for (auto x : p) {
		if (x * x > v)break;
		if (v % x == 0 && v != x)return false;
	}
	return true;
}
vector<ll>build_to_k(ll k, map<ll, vector<ll>>mp, map<ll, vector<ll>>inf) {
	vector<ll>ans;
	if (k % 2 == 0) {
		for (auto &x : mp) {
			if (k == 0)break;
			k -= 2;
			ans.push_back(x.second.back());
			x.second.pop_back();
			ans.push_back(x.second.back());
			x.second.pop_back();
		}
		for (auto& x : mp) {
			while (k != 0 && !x.second.empty()) {
				--k;
				ans.push_back(x.second.back());
				x.second.pop_back();
			}
		}
		for (auto x : inf) {
			if (k) {
				--k;
				ans.push_back(x.first);
			}
		}
		return ans;
	}
	ll mn = INF;
	for (auto x : mp)if (x.second.size() != 2)mn = 1;
	for (auto x : inf)mn = min(mn, (ll)x.second.size());
	if (mn * 2 > k)return ans;
	if (mn == 1) {
		for (auto& x : mp) {
			if (x.second.size() != 2) {
				k -= 3;
				for (int j = 0; j < 3; ++j) {
					ans.push_back(x.second.back());
					x.second.pop_back();
				}
				break;
			}
		}
	}
	else {
		ll to_del = -1;
		for (auto x : inf) {
			if (x.second.size() == mn) {
				to_del = x.first;
				k -= 2 * mn + 1;
				ans.push_back(x.first);
				for (auto prime : x.second) {
					for (int j = 0; j < 2; ++j) {
						ans.push_back(mp[prime].back());
						mp[prime].pop_back();
					}
				}
				break;
			}
		}
		inf.erase(to_del);
	}
	for (auto &x : mp) {
		if (k == 0)break;
		if (x.second.size() >= 2) {
			k -= 2;
			ans.push_back(x.second.back());
			x.second.pop_back();
			ans.push_back(x.second.back());
			x.second.pop_back();
		}
	}
	for (auto& x : mp) {
		while (!x.second.empty() && k != 0) {
			--k;
			ans.push_back(x.second.back());
			x.second.pop_back();
		}
	}
	for (auto& x : inf) {
		if (k) {
			--k;
			ans.push_back(x.first);
		}
	}
	return ans;
}
void solve() {
	int n, k;
	cin >> n >> k;
	map<ll, vector<ll>>mp;
	vector<ll>a(n);
	for (auto& x : a)cin >> x;
	for (auto x : a) {
		ll remember = x;
		if (x <= 2e9 && is_it_prime(x)) {
			mp[x].push_back(x);
			continue;
		}
		int ct = 0;
		for (auto d : p) {
			if (x % d == 0) {
				ct = 1;
				while (x % d == 0)x /= d;
				if (x == 1) {
					mp[d].push_back(remember);
				}
				break;
			}
		}
		if (ct)continue;
		ll b = 1, e = 2e9;
		while (b + 1 != e) {
			ll m = (b + e) / 2;
			if (m * m <= remember) {
				b = m;
			}
			else e = m;
		}
		if (b * b == x && is_it_prime(b))mp[b].push_back(remember);
	}
	map<ll, vector<ll>>inf_about_dig;
	vector<ll>to_erase;
	for (auto x : mp)if (x.second.size() == 1)to_erase.push_back(x.first);
	for (auto x : to_erase)mp.erase(x);
	for (auto c : a) {
		ll rm = c;
		vector<ll>zaebic;
		for (auto x : mp) {
			if (c % x.first == 0) {
				zaebic.push_back(x.first);
				while (c % x.first == 0)c /= x.first;
			}
		}
		if (c > 1 || zaebic.size() == 1)continue;
		inf_about_dig[rm] = zaebic;
	}
	vector<ll>ans = build_to_k(k, mp, inf_about_dig);
	if (ans.size() != k) {
		cout << "0\n";
		return;
	}
	sort(ans.begin(), ans.end());
	for (auto x : ans)cout << x << " "; cout << "\n";
}
int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cout.precision(10);
#ifdef _DEBUG
	freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
#else
	//freopen("epic.in", "r", stdin); freopen("epic.out", "w", stdout);
#endif
	int t = 1;
	build_prime();
	//cin >> t;
	while (t--) {
		solve();
	}
	return 0;
}