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
// #define FILE_IN_OUT
#define RET(_x)    return cout << (_x) << '\n', 0;
#define all(_obj)  (_obj).begin(), (_obj).end()
#define loop(_n)   for (int i = 0; i < (_n); ++i)
#define sz(_obj)   static_cast<int>((_obj).size())
#ifdef SHJ_LOCAL
#define debug(_x)  std::cerr << (#_x) << " = " << (_x) << '\n' << std::flush;
#else
#define debug(_x)  {}
#endif
#define endl "\n"
template<typename P, typename Q>
inline P CeilDiv(P _dividend, Q _divider) {
    return static_cast<P>((_dividend - 1LL + _divider) / _divider);
}
template<typename Tp>
inline void outarr(Tp _begin, Tp _end, const char* _delim = " ") {
    for (Tp current = _begin; current != _end; ++current) {
        std::cout << *current << _delim;
    }
    std::cout << '\n';
}

//.constant
using ll = int64_t;
using pii = std::pair<int, int>;
constexpr int INF = 0x3f3f3f3f;
constexpr int MOD = static_cast<int>(1e9 + 7);

//.data
constexpr int MAXN = 1000000;

bool noprime[MAXN + 1];

void Sieve() {
    noprime[0] = noprime[1] = true;
    for (int i = 2; i * i <= MAXN; ++i) {
        if (!noprime[i]) {
            for (int j = i * i; j <= MAXN; j += i) {
                noprime[j] = true;
            }
        }
    }
}

bool IsPrime(int x) {
    if ((x & 1) == 0) {
        return false;
    }
    for (int i = 3; i * i <= x; i += 2) {
        if (x % i == 0) {
            return false;
        }
    }
    return true;
}

//.code
int main() {
#ifdef FILE_IN_OUT
    std::ifstream cin ("input.txt",  std::ios::in);
    std::ofstream cout("output.txt", std::ios::out);
#else
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
#endif

    int n, k;
    cin >> n >> k;
    if (k == 1) {
        RET(0);
    }
    vector<ll> arr(n);
    loop(n) {
        cin >> arr[i];
    }
    Sieve();
    unordered_set<ll> nums(all(arr));
    map<int, vector<ll>> vec;
    for (int p = 2; p < MAXN; ++p) {
        if (noprime[p]) {
            continue;
        }
        vector<ll> cur;
        for (ll x = 1; x <= ll(1e18) / p;) {
            x *= p;
            if (nums.count(x) && sz(cur) < 2) {
                cur.push_back(x);
            }
        }
        if (sz(cur) > 1) {
            vec[p] = move(cur);
        }
    }
    for (ll x : arr) {
        if (ll(1e6) < x && x < ll(1e9) && nums.count(x * x) && IsPrime((int)x)) {
            vec[(int)x] = {x, x * x};
        }
    }
    if (2 * sz(vec) <= k || (k & 1) == 0) {
        vector<ll> ans;
        for (const auto& kv : vec) {
            ans.insert(ans.end(), all(kv.second));
            if (sz(ans) == k) {
                break;
            }
            nums.erase(kv.second[0]);
            nums.erase(kv.second[1]);
        }
        for (ll x : nums) {
            if (sz(ans) == k) {
                break;
            }
            ll y = x;
            for (const auto& kv : vec) {
                while (x % kv.first == 0) {
                    x /= kv.first;
                }
            }
            if (x == 1) {
                ans.push_back(y);
            }
        }
        if (sz(ans) < k) {
            RET(0);
        }
        outarr(all(ans));
        return 0;
    }
    for (const auto& kv : vec) {
        nums.erase(kv.second[0]);
        nums.erase(kv.second[1]);
    }
    ll val = -1;
    for (ll x : nums) {
        ll y = x;
        int cnt = 0;
        for (const auto& kv : vec) {
            if (x % kv.first == 0) {
                ++cnt;
                while (x % kv.first == 0) {
                    x /= kv.first;
                }
            }
        }
        if (x == 1 && cnt <= k / 2) {
            val = y;
            break;
        }
    }
    if (val == -1) {
        RET(0);
    }
    vector<ll> ans{val};
    vector<ll> tmp;
    for (const auto& kv : vec) {
        if (val % kv.first == 0) {
            ans.insert(end(ans), all(kv.second));
        } else {
            tmp.insert(end(tmp), all(kv.second));
        }
    }
    while (sz(ans) < k) {
        ans.push_back(tmp.back());
        tmp.pop_back();
    }
    outarr(all(ans));

#ifdef FILE_IN_OUT
    cin.close();
    cout.close();
#endif
    return 0;
}