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 JAVA):

Solution:
//package com.company;

import java.io.*;
import java.math.*;
import java.util.*;

public class Main {
    public static class Task {

        int[] factor;
        List<Integer> primes;

        void ini() {
            int N = 1000010;
            factor = new int[N];
            primes = new ArrayList<>();
            for (int i = 2; i < N; i++) {
                if (factor[i] == 0) {
                    factor[i] = i;
                    primes.add(i);
                }
                for (int j: primes) {
                    if (i * j >= N) break;
                    factor[i * j] = j;
                    if (i % j == 0) break;
                }
            }
        }

        long findSQRT(long x) {
            long lo = 0, hi = 1000000000;
            while (lo < hi) {
                long mid = (lo + hi) / 2;
                if (mid * mid < x) {
                    lo = mid + 1;
                } else {
                    hi = mid;
                }
            }
            if (lo * lo == x) return lo;
            return -1;
        }

        long findTQRT(long x) {
            long lo = 0, hi = 1000000;
            while (lo < hi) {
                long mid = (lo + hi) / 2;
                if (mid * mid * mid < x) {
                    lo = mid + 1;
                } else {
                    hi = mid;
                }
            }
            if (lo * lo * lo == x) return lo;
            return -1;
        }

        boolean isPrime(long x) {
            if (x > 1000000) {
                return BigInteger.valueOf(x).isProbablePrime(100);
            }
            return factor[(int) x] == x;
        }

        List<Long> tryFactor(List<Map.Entry<Long, List<Long>>> entries, long x) {
            List<Long> factors = new ArrayList<>();
            for (Map.Entry<Long, List<Long>> e: entries) {
                long k = e.getKey();
                if (x % k == 0) {
                    while (x % k == 0) x /= k;
                    factors.add(k);
                }
            }
            if (x == 1) return factors;
            return null;
        }

        public void solve(Scanner sc, PrintWriter pw) throws IOException {
            ini();
            int n = sc.nextInt();
            int k = sc.nextInt();
            if (k == 1) {
                pw.println(0);
                return;
            }
            long[] v = new long[n];
            for (int i = 0; i < n; i++) {
                v[i] = sc.nextLong();
            }
            Map<Long, List<Long>> goodNumbers = new HashMap<>();
            boolean[] inGood = new boolean[n];
            for (int i = 0; i < n; i++) {
                {
                    if (isPrime(v[i])) {
                        if (!goodNumbers.containsKey(v[i])) goodNumbers.put(v[i], new ArrayList<>());
                        goodNumbers.get(v[i]).add(v[i]);
                        inGood[i] = true;
                    }
                }
                if (inGood[i]) continue;
                {
                    long psqrt = findSQRT(v[i]);
                    if (psqrt != -1) {
                        if (isPrime(psqrt)) {
                            if (!goodNumbers.containsKey(psqrt)) goodNumbers.put(psqrt, new ArrayList<>());
                            goodNumbers.get(psqrt).add(v[i]);
                            inGood[i] = true;
                        }
                    }
                }
                if (inGood[i]) continue;
                {
                    long ptqrt = findTQRT(v[i]);
                    if (ptqrt != -1) {
                        if (isPrime(ptqrt)) {
                            if (!goodNumbers.containsKey(ptqrt)) goodNumbers.put(ptqrt, new ArrayList<>());
                            goodNumbers.get(ptqrt).add(v[i]);
                            inGood[i] = true;
                        }
                    }
                }
                if (inGood[i]) continue;
                for (int p: primes) {
                    if (p * p * p > v[i]) break;
                    if (v[i] % p == 0) {
                        long y = v[i];
                        while (y % p == 0) {
                            y /= p;
                        }
                        if (y == 1) {
                            if (!goodNumbers.containsKey((long)p)) goodNumbers.put((long) p, new ArrayList<>());
                            goodNumbers.get((long)p).add(v[i]);
                            inGood[i] = true;
                        }
                        break;
                    }
                }
            }
            Map<Long, Integer> mapLoc = new HashMap<>();
            Set<Long> onlyOnes = new HashSet<>();
            for (int i = 0; i < n; i++) {
                mapLoc.put(v[i], i);
            }
            for (Long key: goodNumbers.keySet()) {
                if (goodNumbers.get(key).size() == 1) {
                    onlyOnes.add(key);
                }
            }
            for (Long key: onlyOnes) {
                inGood[mapLoc.get(goodNumbers.get(key).get(0))] = false;
                goodNumbers.remove(key);
            }
            int totalGood = 0;
            for (Long key: goodNumbers.keySet()) {
                totalGood += goodNumbers.get(key).size();
            }
            if (k < totalGood) {
                List<Map.Entry<Long, List<Long>>> entries = new ArrayList<>(goodNumbers.entrySet());
                entries.sort(new Comparator<Map.Entry<Long, List<Long>>>() {
                    @Override
                    public int compare(Map.Entry<Long, List<Long>> o1, Map.Entry<Long, List<Long>> o2) {
                        return o1.getValue().size() - o2.getValue().size();
                    }
                });
                int np = entries.size();

                if (entries.get(np - 1).getValue().size() > 2) {
                    List<Long> ret = new ArrayList<>();
                    int r = k;
                    for (int i = 0; i < np; i++) {
                        int c = entries.get(i).getValue().size();
                        if (r <= 1) throw new RuntimeException();
                        if (c >= r) {
                            for (int j = 0; j < r; j++) {
                                ret.add(entries.get(i).getValue().get(j));
                            }
                            r = 0;
                            break;
                        } else if (c + 1 < r) {
                            r -= c;
                            ret.addAll(entries.get(i).getValue());
                        } else {
                            if (r == 3) {
                                for (int j = 0; j < r; j++) {
                                    ret.add(entries.get(np - 1).getValue().get(j));
                                }
                                r = 0;
                                break;
                            } else {
                                for (int j = 0; j < c - 1; j++) {
                                    ret.add(entries.get(i).getValue().get(j));
                                }
                                r -= (c - 1);
                            }
                        }
                    }
                    for (long x: ret) {
                        pw.print(x + " ");
                    }
                    pw.println();
                } else {
                    List<Long> ret = new ArrayList<>();
                    if (k % 2 == 0) {
                        for (int i = 0; i < k / 2; i++) {
                            ret.addAll(entries.get(i).getValue());
                        }
                    } else {
                        for (int i = 0; i < n; i++) {
                            if (inGood[i]) continue;
                            List<Long> f = tryFactor(entries, v[i]);
                            if (f != null && f.size() <= k / 2) {
                                Set<Long> used = new HashSet<>(f);
                                ret.add(v[i]);
                                for (long x: f) {
                                    ret.addAll(goodNumbers.get(x));
                                }
                                for (Map.Entry<Long, List<Long>> en: entries) {
                                    if (ret.size() >= k) break;
                                    if (used.contains(en.getKey())) continue;
                                    ret.addAll(en.getValue());
                                }
                                break;
                            }
                        }
                    }
                    if (ret.size() == 0) {
                        pw.println(0);
                    } else {
                        for (long x: ret) {
                            pw.print(x + " ");
                        }
                        pw.println();
                    }
                }
            } else {
                List<Map.Entry<Long, List<Long>>> entries = new ArrayList<>(goodNumbers.entrySet());
                int np = entries.size();
                List<Long> ret = new ArrayList<>();
                for (int i = 0; i < np; i++) {
                    ret.addAll(entries.get(i).getValue());
                }
                for (int i = 0; i < n; i++) {
                    if (ret.size() == k) break;
                    if (inGood[i]) continue;
                    List<Long> f = tryFactor(entries, v[i]);
                    if (f != null) {
                        ret.add(v[i]);
                    }
                }
                if (ret.size() < k) {
                    pw.println(0);
                } else {
                    for (long x: ret) {
                        pw.print(x + " ");
                    }
                    pw.println();
                }
            }
        }
    }

    static long TIME_START, TIME_END;

    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
//        Scanner sc = new Scanner(new FileInputStream("in.txt"));
        PrintWriter pw = new PrintWriter(new BufferedOutputStream(System.out)); //output
//        PrintWriter pw = new PrintWriter(new FileOutputStream("out.txt"));
        Runtime runtime = Runtime.getRuntime();
        long usedMemoryBefore = runtime.totalMemory() - runtime.freeMemory();
        TIME_START = System.currentTimeMillis();
        Task t = new Task();
        t.solve(sc, pw);
        TIME_END = System.currentTimeMillis();
        long usedMemoryAfter = runtime.totalMemory() - runtime.freeMemory();
        pw.close();
        System.err.println("Memory increased: " + (usedMemoryAfter - usedMemoryBefore) / 1000000);
        System.err.println("Time used: " + (TIME_END - TIME_START) + ".");
    }

    static class Scanner {
        StringTokenizer st;
        BufferedReader br;

        public Scanner(InputStream s) {
            br = new BufferedReader(new InputStreamReader(s));
        }

        public Scanner(FileReader s) throws FileNotFoundException {
            br = new BufferedReader(s);
        }

        public String next() throws IOException {
            while (st == null || !st.hasMoreTokens())
                st = new StringTokenizer(br.readLine());
            return st.nextToken();
        }

        public int nextInt() throws IOException {
            return Integer.parseInt(next());
        }

        public long nextLong() throws IOException {
            return Long.parseLong(next());
        }

        public String nextLine() throws IOException {
            return br.readLine();
        }

        public double nextDouble() throws IOException {
            return Double.parseDouble(next());
        }

        public boolean ready() throws IOException {
            return br.ready();
        }
    }
}