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:
//Codeforces Template
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
template<class T, class S>
ostream& operator << (ostream &o, const pair<T, S> &p) {
    return o << '(' << p.first << ", " << p.second << ')';
}
template<template<class, class...> class T, class... A>
typename enable_if<!is_same<T<A...>, string>(), ostream&>::type
operator << (ostream &o, T<A...> V) {
	o << '[';
	for(auto a : V) o << a << ", ";
	return o << ']';
}

typedef long long int ll;
typedef long double ld;
typedef pair<ll, ll> pl;

#define G(x) ll x; cin >> x;
#define GD(x) ld x; cin >> x;
#define GS(s) string s; cin >> s;
#define F(i, l, r) for(ll i = l; i < (r); ++i)
#define FD(i, r, l) for(ll i = r; i > (l); --i)
#define P(a, n) { cout << "{ "; F(_, 0, n) cout << a[_] << " "; cout << "}\n"; }
#define EX(x) { cout << x << '\n'; exit(0); }
#define A(a) (a).begin(), (a).end()
#define K first
#define V second
#define M 1000000007 //998244353
#define N 1010

using u128 = ll;//__uint128_t;

ll binpower(ll base, ll e, ll mod) {
    ll result = 1;
    base %= mod;
    while (e) {
        if (e & 1)
            result = (u128)result * base % mod;
        base = (u128)base * base % mod;
        e >>= 1;
    }
    return result;
}

bool check_composite(ll n, ll a, ll d, int s) {
    ll x = binpower(a, d, n);
    if (x == 1 || x == n - 1)
        return false;
    for (int r = 1; r < s; r++) {
        x = (u128)x * x % n;
        if (x == n - 1)
            return false;
    }
    return true;
};

bool MillerRabin(ll n) { // returns true if n is prime, else returns false.
    if (n < 2)
        return false;

    int r = 0;
    ll d = n - 1;
    while ((d & 1) == 0) {
        d >>= 1;
        r++;
    }

    for (int a : {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37}) {
        if (n == a)
            return true;
        if (check_composite(n, a, d, r))
            return false;
    }
    return true;
}

map<ll, vector<ll>> plist;
vector<ll> notpw, oknotpw;
ll x[N];

ll pw(ll a, ll p) { return p ? a * pw(a, p - 1) : 1; }

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    G(n) G(k)
    F(i, 0, n) {
        cin >> x[i];
        ll xpw = -1;
        F(p, 1, 100) {
            if(x[i] >> p) {
                ld y = (ll)round(powl((ld)x[i], 1 / (ld)p));
                F(z, y - 10, y + 10)
                    if(pw(z, p) == x[i] && MillerRabin(z)) xpw = z;
            }
        }
        if(~xpw) plist[xpw].push_back(x[i]);
        else notpw.push_back(x[i]);
    }
    vector<ll> rlist;
    for(auto a : plist) if(a.V.size() < 2) rlist.push_back(a.K);
    for(ll r : rlist) plist.erase(r);
    ll bestSpare = -1;
    set<ll> bstSet;
    for(ll z : notpw) {
        ll temp = z;
        set<ll> eee;
        for(auto a : plist) while(!(temp % a.K)) temp /= a.K, eee.insert(a.K);
        if(temp == 1) {
            oknotpw.push_back(z);
            if(eee.size() < bstSet.size() || bstSet.empty()) bestSpare = z, bstSet = eee;
        }
    }
    vector<ll> ans;
    bool flag = false;
    //cout << plist << '\n';
    ll reeeee = -1;
    if(k & 1) {
        for(auto& a : plist) if(a.V.size() >= 3) {
            F(i, 0, 3) ans.push_back(a.V.back()), a.V.pop_back();
            reeeee = a.K;
            break;
        }
        if(ans.empty()) {
            if(bstSet.size() && k >= 1 + 2 * bstSet.size()) {
                ans.push_back(bestSpare);
                flag = true;
                for(ll e : bstSet) F(j, 0, 2) ans.push_back(plist[e].back()), plist[e].pop_back();
            } else EX(0)
        }
    }
    //cout << plist << '\n';
    for(auto& a : plist) if(ans.size() + 2 <= k && a.V.size() >= 2 && a.K - reeeee)
        F(i, 0, 2) ans.push_back(a.V.back()), a.V.pop_back();
    //cout << plist << '\n';
    for(auto& a : plist) while(ans.size() < k && a.V.size()) ans.push_back(a.V.back()), a.V.pop_back();
    //cout << plist << '\n';
    for(ll x : oknotpw) {
        if(flag && x == bestSpare) { flag = false; continue; }
        if(ans.size() < k) ans.push_back(x);
    }
    if(ans.size() != k) EX(0)
    F(i, 0, k) cout << ans[i] << ' ';
}