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:
#ifndef _MY
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,abm,mmx,tune=native")
#endif
#include "bits/stdc++.h"
#define int ll
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;
typedef long double ld;
const int64_t INF = (int64_t)(2e18);
const int inf = (int)(1e9 + 7);
const int maxn = 500 * 1000 + 100;
chrono::time_point<chrono::steady_clock> cl;
double current_time() { return (double)(chrono::steady_clock::now() - cl).count() / 1e9; }
//------------------------------------------//




int32_t main(){
    cl = chrono::steady_clock::now();
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(10);
    cin.tie(nullptr);
#ifdef _MY
    freopen("VimProject/input.txt", "r", stdin);
    freopen("VimProject/output.txt", "w", stdout);
#endif

    int n, k;
    cin >> n >> k;
    if (k == 1) {
        cout << 0;
        return 0;
    }
    vector<int> a(n);
    vector<int> sieve(1300000, 1);
    sieve[0] = sieve[1] = 0;
    vector<int> primes;
    map<int, vector<int>> ma;
    vector<pair<int, vector<int>>> gen;
    for (int i = 2; i < (int)sieve.size(); ++i){
        if (sieve[i] == 0) continue;
        primes.push_back(i);
        for (int j = 2*i; j < (int)sieve.size(); j += i)
            sieve[j] = 0;
    }

    auto isprime = [&](int aa)->bool{
        if (aa > ll(100000)*ll(100000)) return false;
        if (aa == 1) return false;
        for (int i = 2; i * i <= aa; ++i){
            if (aa % i == 0) return false;
        }
        return true;
    };
    for (auto& it : a) cin >> it;
    for (auto& it : a){
        int cur = it;
        int rt = (int)sqrt((double)cur+0.1);
        if (rt*rt == cur && isprime(rt)) 
            ma[rt].push_back(cur);
        else{
            //cout << cur << endl;
            map<int, int> dec;
            for (auto& p : primes){
                if (p*p > cur) break;
                while(cur % p == 0) {
                    dec[p]++;
                    cur /= p;
                }
            }
            if (isprime(cur)) {
                dec[cur]++;
                cur = 1;
            }
            //for (auto& it : dec) cout << it.first << " " << it.second << endl;
            if (cur != 1) continue;
            if (dec.size() == 0) continue;
            if (dec.size() == 1) ma[dec.begin()->first].push_back(it);
            if (dec.size() >= 2) {
                gen.push_back(make_pair(it, vector<int>()));
                for (auto& itt : dec) gen.back().second.push_back(itt.first);
            }
        }
    }
    //for (auto& it : ma) {
    //    cout << it.first << ": ";
    //    for (auto& itt : it.second) cout << itt << " ";
    //    cout << endl;
    //}
    vector<int> bad;
    for (auto& it : ma){
        sort(all(it.second));
        if (it.second.size() == 1) 
            bad.push_back(it.first);
    }
    for (auto& it : bad) ma.erase(it);

    vector<int> res;
    int cnt = 0;
    for (auto& it : ma) cnt += (int)it.second.size();
    if (cnt <= k){
        for (auto& it : ma){
            for (auto& itt : it.second)
                res.push_back(itt);
        }
        for (auto& it : gen){
            if ((int)res.size() == k) break;
            bool good = true;
            for (auto& itt : it.second)
                if (ma.count(itt) == 0) good = false;
            if (good) res.push_back(it.first);
        }
        if ((int)res.size() != k) cout << 0;
        else for (auto& it : res) cout << it << " ";
        return 0;
    } else{
        for (auto& it : ma) reverse(all(it.second));
        if (k % 2 == 0){
            for (auto& it : ma) {
                if ((int)res.size() == k) break;
                for (int i = 0; i < 2; ++i){
                    res.push_back(it.second.back());
                    it.second.pop_back();
                }
            }
            for (auto& it : ma){
                for (auto& itt : it.second){
                    if ((int)res.size() == k) break;
                    res.push_back(itt);
                    it.second.pop_back();
                }
            }
            for (auto& it: res) cout << it << " ";
            return 0;
        } else {
            int ok = -1;
            for (auto& it : ma){
                if (ok != -1) break;
                if (it.second.size() > 2) ok = it.first;
            }
            if (ok != -1){
                for (int i = 0; i < 3; ++i){
                    res.push_back(ma[ok].back());
                    ma[ok].pop_back();
                }
                for (auto& it : ma){
                    if (it.first == ok) continue;
                    if ((int)res.size() == k) break;
                    for (int i = 0; i < 2; ++i){
                        res.push_back(it.second.back());
                        it.second.pop_back();
                    }
                }
                for (auto& it : ma){
                    for (auto& itt : it.second){
                        if ((int)res.size() == k) break;
                        res.push_back(itt);
                    }
                }
                for (auto& it : res) cout << it << " ";
            } else{
                pair<int, vector<int>> fine(-1, vector<int>());
                for (auto& it : gen){
                    bool good = true;
                    for (auto& itt : it.second)
                        if (ma.count(itt) == 0) good = false;
                    if (!good) continue;
                    if (fine.first == -1 || fine.second.size() > it.second.size())
                        fine = it;
                }
                if (fine.first == -1) {
                    cout << 0;
                    return 0;
                }
                res.push_back(fine.first);
                set<int> used;
                for (auto& it : fine.second){
                    used.insert(it);
                    for (int i = 0; i < 2; ++i){
                        res.push_back(ma[it].back());
                        ma[it].pop_back();
                    }
                }
                if ((int)res.size() > k){
                    cout << 0;
                    return 0;
                }
                for (auto& it : ma){
                    if (used.count(it.first)) continue;
                    if ((int)res.size() == k) break;
                    for (int i = 0; i < 2; ++i){
                        res.push_back(it.second.back());
                        it.second.pop_back();
                    }
                }
                for (auto& it : ma){
                    for (auto& itt : it.second){
                        if ((int)res.size() == k) break;
                        res.push_back(itt);
                    }
                }
                for (auto& it : res) cout << it << " ";
            }
        }

    }


    return 0;
}