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;

const int B = 60;
int low[B + 3], high[B + 3];

const int N = 1003;
long long A[N], primes[N];

int isperf[N], isok[N];

// factors[i] = set of primes facs of A[i]
vector<long long> factors[N];
// ppow[P] = set of indices i such that A[i] = P^k for some k > 0
map<long long, vector<int>> ppow;

// set of prime powers - pset[i]
vector<long long> pset[N];
// pointer for each vector of pset (used only for output)
int pset_ptr[N];
// index i such that size(pset[i]) > 2
int g2psetidx = -1;

// composite numbers
long long cset[N];
// number of distinct prime facs of cset[i]
int facsize[N];

long long fexp(long long base, long long exp) {
    long long result = 1;
    while (exp > 0) {
        if (exp % 2 == 1) result = (result * base);
        exp >>= 1;
        base = (base * base);
    }
    return result;
}

long long modpow(long long base, long long exp, long long mod) {
    if (base >= mod) base %= mod;

    long long result = 1;
    while (exp > 0) {
        if (exp % 2 == 1) result = (result * base) % mod;
        exp >>= 1;
        base = (base * base) % mod;
    }
    return result;
}

int miller_rabin(long long n) {
    if (n == 1LL) return 0;
    
    vector<int> rng = {2, 3, 5, 7, 11, 13, 17, 19, 23};
    
    if (find(rng.begin(), rng.end(), n) != rng.end()) return 1;
    
    long long d = n - 1;
    int r = 0;
    
    while (d % 2 == 0) {
        d /= 2;
        r += 1;
    }
    
    for (int a : rng) {
        long long x = modpow(a * 1LL, d, n);
        
        if (x == 1LL or x == n - 1) continue;
        
        for (int i = 0; i < r - 1; i++) {
            long long y = (x * x) % n;
            
            if (y == 1) return 0; //__gcd(x - 1, n);
            
            x = y;
            
            if (x == n - 1) break;
        }
        
        if (x == n - 1) continue;
        
        return 0;
    }
    
    return 1;
}

int main() {    
    int n, K; scanf("%d%d", &n, &K);

    for (int i = 0; i < n; i++) scanf("%lld", &A[i]);

    // fill the lows and highs
    for (int i = 2; i < B; i++) low[i] = 1;

    // the highs
    high[2] = 1000000000;
    high[3] = 1000000;
    high[4] = 31622;
    high[5] = 3981;
    high[6] = 1000;
    high[7] = 372;
    high[8] = 177;
    high[9] = 100;
    high[10] = 63;
    high[11] = 43;
    high[12] = 31;
    high[13] = 24;
    high[14] = 19;
    high[15] = 15;
    high[16] = 13;
    high[17] = 11;
    high[18] = 10;
    high[19] = 8;

    high[20] = high[21] = 7;
    high[22] = high[23] = 6;
    high[24] = high[25] = 5;

    for (int i = 26; i < 30; i++) high[i] = 4;
    for (int i = 30; i < 38; i++) high[i] = 3;
    for (int i = 38; i < 60; i++) high[i] = 2;
    
    int primes_ptr = 0; // ptr for primes[] array

    // time to do binary search
    for (int i = 0; i < n; i++) {
        int flag = 0;
        for (int k = B - 1; k > 1; k--) {
            // hi should not be achievable!
            int lo = low[k], hi = high[k] + 1;
            while (lo < hi) {
                int mid = lo + (hi - lo) / 2;

                long long res = fexp(mid * 1LL, k);

                if (res == A[i]) {
                    flag = 1;
                    
                    if (miller_rabin(mid * 1LL) == 1) {
                        factors[i].push_back(mid * 1LL);
                        
                        ppow[mid * 1LL].push_back(i);
                        isperf[i] = 1;
                        
                        if ((int)ppow[mid * 1LL].size() == 1) primes[primes_ptr++] = (mid * 1LL);
                    }

                    break;
                }

                if (res < A[i]) lo = mid + 1;
                else hi = mid;
            }
            if (flag) break;
        }
    }

    // find out primes and composites
    for (int i = 0; i < n; i++) {
        if (isperf[i]) continue;
        
        long long x = A[i];
        for (int j = 0; j < primes_ptr; j++) {
            long long P = primes[j];
            
            if (x % P == 0) {
                factors[i].push_back(P);
                
                x /= P;
                while (x % P == 0) x /= P;
            }
        }
        
        if (x == 1) {
            if ((int)factors[i].size() == 1) { // it's a prime number (p ^ 1)
                ppow[A[i]].push_back(i);
                isperf[i] = 1;
            }
            else isok[i] = 1;
        }
    }

    // count of "good" numbers
    int T = 0;
    
    // eliminate primes with only 1 occurrence
    int last_occ = -1;
    for (int i = 0; i < primes_ptr; i++) {
        int sz = (int)ppow[primes[i]].size();

        if (sz < 2) primes[i] = 0;
        else {
            T += sz; // it's good :)

            int j = i;
            while (j > 0) {
                if (primes[j - 1] == 0) {
                    primes[j - 1] = primes[j];
                    primes[j] = 0;

                    j = j - 1;
                }
                else break;
            }
            last_occ = j;

            // are you the one?
            if (sz > 2) g2psetidx = j;

            // fill pset[]
            for (int it = 0; it < sz; it++) {
                pset[j].push_back(A[ppow[primes[j]][it]]);
            }
        }
    }

    primes_ptr = last_occ + 1; // number of "good" primes

    // ptr for cset[]
    int cset_ptr = 0;

    // fill cset
    for (int i = 0; i < n; i++) {
        if (!isok[i]) continue;

        for (long long p : factors[i]) {
            if ((int)ppow[p].size() < 2) {
                isok[i] = 0;
                break;
            }
        }

        // "good" composite number
        if (isok[i]) {
            facsize[cset_ptr] = (int)factors[i].size();
            cset[cset_ptr++] = A[i];
        }
    }

    int gPcnt = T; // count of "good" prime powers only
    T += cset_ptr; // good non-(prime powers) added to total

    if (gPcnt == 0) { // must have atleast one "good" prime
        printf("0\n");
        return 0;
    }

    if (K > T) { // more than total => not possible
        printf("0\n");
        return 0;
    }

    if (K >= gPcnt) { // can take all primes
        int cntr = 0;

        // print all the prime powers first
        for (int i = 0; i < primes_ptr; i++) {
            for (auto x : pset[i]) printf("%lld ", x);
            cntr += pset[i].size();
        }

        // print the composites till we hit K
        for (int i = 0; cntr != K; cntr++, i++) {
            printf("%lld ", cset[i]);
        }

        return 0;
    }

    if (K >= (2 * primes_ptr)) { // take atleast 2 from each prime first
        for (int i = 0; i < primes_ptr; i++) {
            printf("%lld %lld ", pset[i][0], pset[i][1]); // print 2 each
            pset_ptr[i] = 2; // where to start printing from
        }

        int cntr = 2 * primes_ptr;
        for (int i = 0; cntr != K; ) {
            while (cntr < K && pset_ptr[i] < pset[i].size()) {
                printf("%lld ", pset[i][pset_ptr[i]++]);
                cntr++;
            }
            i++; 
        }

        return 0;
    }

    if (K % 2 == 0) { // print 2 each from (K / 2) primes
        int up = (K / 2);

        for (int i = 0; i < up; i++) {
            printf("%lld %lld ", pset[i][0], pset[i][1]);
        }

        return 0;
    }

    if (K == 1) {
        printf("0\n");
        return 0;
    }

    // now K is odd such that 3 < K < 2 * primes_ptr
    if (g2psetidx != -1) { // the savior exists
        K -= 3;

        printf("%lld %lld %lld ", pset[g2psetidx][0], pset[g2psetidx][1], pset[g2psetidx][2]);
        pset_ptr[g2psetidx] = 3;

        int up = (K / 2);
        int cntr = 0;
        for (int i = 0; i < primes_ptr; i++) {
            if (i == g2psetidx) continue;

            printf("%lld %lld ", pset[i][0], pset[i][1]);
            cntr += 2;

            if (cntr == K) return 0;
        }
    }

    // the savior doesn't exist, can a composite save us?
    int t = n; // min number of primes it depends on, initialize with "infinity"
    for (int i = 0; i < cset_ptr; i++) t = min(t, facsize[i]);
    
    if (K < (1 + 2 * t)) {
        printf("0\n");
        return 0;
    }

    long long savior;
    for (int i = 0; i < cset_ptr; i++) {
        if (facsize[i] == t) {
            printf("%lld ", cset[i]);
            savior = cset[i];
            break;
        }
    }

    int cntr = 1;

    for (int i = 0; i < primes_ptr; i++) {
        if (savior % primes[i] == 0) {
            printf("%lld %lld ", pset[i][0], pset[i][1]);
            cntr += 2;
            t -= 1;
        }
        else {
            if (K - cntr > 2 * t) {
                printf("%lld %lld ", pset[i][0], pset[i][1]);
                cntr += 2;
            }
        }
    }

    return 0;
}