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:
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.util.Arrays;
import java.util.HashMap;
import java.nio.ByteBuffer;
import java.util.ArrayList;
import java.util.HashSet;
import java.nio.charset.Charset;
import java.util.Map;
import java.util.NoSuchElementException;
import java.io.OutputStream;
import java.util.Iterator;
import java.nio.CharBuffer;
import java.util.Set;
import java.io.IOException;
import java.nio.charset.CharsetDecoder;
import java.nio.charset.StandardCharsets;
import java.io.UncheckedIOException;
import java.util.Objects;
import java.util.List;
import java.util.Map.Entry;
import java.io.Writer;
import java.util.Collections;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author mikit
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        LightScanner2 in = new LightScanner2(inputStream);
        LightWriter2 out = new LightWriter2(outputStream);
        LPrimeDivisorsSelection solver = new LPrimeDivisorsSelection();
        solver.solve(1, in, out);
        out.close();
    }

    static class LPrimeDivisorsSelection {
        public void solve(int testNumber, LightScanner2 in, LightWriter2 out) {
            int n = in.ints(), k = in.ints();
            long[] x = in.longs(n);
            IntroSort.sort(x);

            Set<Long> ps = new HashSet<>();
            for (int i = 0; i < n; i++) {
                for (int j = i + 1; j < n; j++) {
                    if (x[j] % x[i] != 0) continue;
                    long a = x[i], b = x[j];

                    long t = Math.min(a, b / a);
                    Map<Long, Integer> pf = IntMath.primeFactorize(t);
                    if (pf.size() > 1) continue;

                    long p = pf.keySet().iterator().next();
                    if (ps.contains(p)) continue;

                    while (a % p == 0) a /= p;
                    while (b % p == 0) b /= p;
                    if (a == 1 && b == 1) ps.add(p);
                }
            }

            Map<Long, List<Long>> pures = new HashMap<>();
            long adj = -1;
            List<Long> adjFactors = null;

            int[] type = new int[n]; // 0: invalid, 1: pure, 2: compound

            int vcnt = 0;
            for (int i = 0; i < n; i++) {
                List<Long> pf = new ArrayList<>();
                long t = x[i];
                for (long p : ps) {
                    if (t % p != 0) continue;
                    pf.add(p);
                    while (t % p == 0) t /= p;
                }
                if (t != 1) continue;
                vcnt++;
                type[i] = 2;

                if (pf.size() == 1) {
                    long p = pf.get(0);
                    if (!pures.containsKey(p)) pures.put(p, new ArrayList<>());
                    if (pures.get(p).size() < 2) {
                        type[i] = 1;
                        pures.get(p).add(x[i]);
                    } else {
                        if (adjFactors == null || 1 < adjFactors.size()) {
                            adj = x[i];
                            adjFactors = Collections.singletonList(p);
                        }
                    }
                } else {
                    if (adjFactors == null || pf.size() < adjFactors.size()) {
                        adj = x[i];
                        adjFactors = pf;
                    }
                }
            }

            if (vcnt < k) {
                out.ans(0);
            } else if (pures.size() * 2 <= k) {
                int rem = k;
                for (List<Long> pp : pures.values()) {
                    if (0 < rem) {
                        out.ans(pp.get(0)).ans(pp.get(1));
                        rem -= 2;
                    }
                }
                for (int i = 0; i < n; i++) {
                    if (0 < rem && type[i] == 2) {
                        out.ans(x[i]);
                        rem--;
                    }
                }

                //if (rem != 0) throw new RuntimeException();
            } else if (k % 2 == 0) {
                int rem = k;
                for (List<Long> pp : pures.values()) {
                    if (0 < rem) {
                        out.ans(pp.get(0)).ans(pp.get(1));
                        rem -= 2;
                    }
                }
                //if (rem != 0) throw new RuntimeException();

            } else if (adj == -1 || k < adjFactors.size() * 2 + 1) {
                out.ans(0);
            } else {
                int rem = k - 1;
                out.ans(adj);
                Set<Long> adjFactorsSet = new HashSet<>(adjFactors);

                for (long p : adjFactors) {
                    List<Long> pp = pures.get(p);
                    out.ans(pp.get(0)).ans(pp.get(1));
                    rem -= 2;
                }

                for (Map.Entry<Long, List<Long>> ent : pures.entrySet()) {
                    if (adjFactorsSet.contains(ent.getKey())) continue;

                    List<Long> pp = ent.getValue();
                    if (0 < rem) {
                        out.ans(pp.get(0)).ans(pp.get(1));
                        rem -= 2;
                    }
                }
                //if (rem != 0) throw new RuntimeException();

            }
            out.ln();
        }

    }

    static class LightScanner2 extends LightScannerAdapter {
        private static final int BUF_SIZE = 16 * 1024;
        private final InputStream stream;
        private final StringBuilder builder = new StringBuilder();
        private final byte[] buf = new byte[BUF_SIZE];
        private int ptr;
        private int len;

        public LightScanner2(InputStream stream) {
            this.stream = stream;
        }

        private int read() {
            if (ptr < len) return buf[ptr++];
            reload();
            if (len == -1) return -1;
            return buf[ptr++];
        }

        private void reload() {
            try {
                ptr = 0;
                len = stream.read(buf);
            } catch (IOException ex) {
                throw new UncheckedIOException(ex);
            }
        }

        private void load(int n) {
            if (ptr + n <= len) return;
            System.arraycopy(buf, ptr, buf, 0, len - ptr);
            len -= ptr;
            ptr = 0;
            try {
                int r = stream.read(buf, len, BUF_SIZE - len);
                if (r == -1) return;
                len += r;
                if (len != BUF_SIZE) buf[len] = '\n';
            } catch (IOException ex) {
                throw new UncheckedIOException(ex);
            }
        }

        private void skip() {
            while (len != -1) {
                while (ptr < len && isTokenSeparator(buf[ptr])) ptr++;
                if (ptr < len) return;
                reload();
            }
            throw new NoSuchElementException("EOF");
        }

        private void loadToken() {
            builder.setLength(0);
            skip();
            for (int b = read(); !isTokenSeparator(b); b = read()) {
                builder.appendCodePoint(b);
            }
        }

        public String string() {
            loadToken();
            return builder.toString();
        }

        public int ints() {
            skip();
            load(12);
            int b = buf[ptr++];
            boolean negate;
            if (b == '-') {
                negate = true;
                b = buf[ptr++];
            } else negate = false;
            int x = 0;
            for (; !isTokenSeparator(b); b = buf[ptr++]) {
                if ('0' <= b && b <= '9') x = x * 10 + b - '0';
                else throw new NumberFormatException("Unexpected character '" + ((char) b) + "'");
            }
            return negate ? -x : x;
        }

        public long longs() {
            skip();
            load(20);
            int b = buf[ptr++];
            boolean negate;
            if (b == '-') {
                negate = true;
                b = buf[ptr++];
            } else negate = false;
            long x = 0;
            for (; !isTokenSeparator(b); b = buf[ptr++]) {
                if ('0' <= b && b <= '9') x = x * 10 + b - '0';
                else throw new NumberFormatException("Unexpected character '" + b + "'");
            }
            return negate ? -x : x;
        }

        public void close() {
            try {
                stream.close();
            } catch (IOException e) {
                throw new UncheckedIOException(e);
            }
        }

        private static boolean isTokenSeparator(int b) {
            return b < 33 || 126 < b;
        }

    }

    static class InsertionSort {
        private InsertionSort() {
        }

        static void sort(long[] a, int low, int high) {
            for (int i = low; i < high; i++) {
                for (int j = i; j > low && a[j - 1] > a[j]; j--) {
                    ArrayUtil.swap(a, j - 1, j);
                }
            }
        }

    }

    static class QuickSort {
        private QuickSort() {
        }

        private static void med(long[] a, int low, int x, int y, int z) {
            if (a[z] < a[x]) {
                ArrayUtil.swap(a, low, x);
            } else if (a[y] < a[z]) {
                ArrayUtil.swap(a, low, y);
            } else {
                ArrayUtil.swap(a, low, z);
            }
        }

        static int step(long[] a, int low, int high) {
            int x = low + 1, y = low + (high - low) / 2, z = high - 1;
            if (a[x] < a[y]) {
                med(a, low, x, y, z);
            } else {
                med(a, low, y, x, z);
            }

            int lb = low + 1, ub = high;
            while (true) {
                while (a[lb] < a[low]) {
                    lb++;
                }
                ub--;
                while (a[low] < a[ub]) {
                    ub--;
                }
                if (lb >= ub) {
                    return lb;
                }
                ArrayUtil.swap(a, lb, ub);
                lb++;
            }
        }

    }

    static class LightWriter2 implements AutoCloseable {
        private static final int BUF_SIZE = 16 * 1024;
        private static final int BUF_THRESHOLD = 1024;
        private final OutputStream out;
        private final byte[] buf = new byte[BUF_SIZE];
        private int ptr;
        private boolean autoflush = false;
        private boolean breaked = true;

        public LightWriter2(OutputStream out) {
            this.out = out;
        }

        public LightWriter2(Writer out) {
            this.out = new LightWriter2.WriterOutputStream(out);
        }

        private void allocate(int n) {
            if (ptr + n <= BUF_SIZE) return;
            try {
                out.write(buf, 0, ptr);
                ptr = 0;
            } catch (IOException ex) {
                throw new UncheckedIOException(ex);
            }
            if (BUF_SIZE < n) throw new IllegalArgumentException("Internal buffer exceeded");
        }

        public void close() {
            try {
                out.write(buf, 0, ptr);
                ptr = 0;
                out.flush();
                out.close();
            } catch (IOException ex) {
                throw new UncheckedIOException(ex);
            }
        }

        public LightWriter2 print(char c) {
            allocate(1);
            buf[ptr++] = (byte) c;
            breaked = false;
            return this;
        }

        public LightWriter2 print(String s) {
            byte[] bytes = s.getBytes();
            int n = bytes.length;
            if (n <= BUF_THRESHOLD) {
                allocate(n);
                System.arraycopy(bytes, 0, buf, ptr, n);
                ptr += n;
                return this;
            }
            try {
                out.write(buf, 0, ptr);
                ptr = 0;
                out.write(bytes);
                out.flush();
            } catch (IOException ex) {
                throw new UncheckedIOException(ex);
            }
            return this;
        }

        public LightWriter2 ans(String s) {
            if (!breaked) print(' ');
            breaked = false;
            return print(s);
        }

        private static int countDigits(int l) {
            if (l >= 1000000000L) return 10;
            if (l >= 100000000L) return 9;
            if (l >= 10000000L) return 8;
            if (l >= 1000000L) return 7;
            if (l >= 100000L) return 6;
            if (l >= 10000L) return 5;
            if (l >= 1000L) return 4;
            if (l >= 100L) return 3;
            if (l >= 10L) return 2;
            return 1;
        }

        private static int countDigits(long l) {
            if (l >= 1000000000000000000L) return 19;
            if (l >= 100000000000000000L) return 18;
            if (l >= 10000000000000000L) return 17;
            if (l >= 1000000000000000L) return 16;
            if (l >= 100000000000000L) return 15;
            if (l >= 10000000000000L) return 14;
            if (l >= 1000000000000L) return 13;
            if (l >= 100000000000L) return 12;
            if (l >= 10000000000L) return 11;
            if (l >= 1000000000L) return 10;
            if (l >= 100000000L) return 9;
            if (l >= 10000000L) return 8;
            if (l >= 1000000L) return 7;
            if (l >= 100000L) return 6;
            if (l >= 10000L) return 5;
            if (l >= 1000L) return 4;
            if (l >= 100L) return 3;
            if (l >= 10L) return 2;
            return 1;
        }

        public LightWriter2 ans(long x) {
            allocate(24);
            if (!breaked) buf[ptr++] = ' ';
            breaked = false;

            if (x < 0) {
                buf[ptr++] = '-';
                x = -x;
            }
            int n = countDigits(x);
            for (int i = ptr + n - 1; ptr <= i; i--) {
                buf[i] = (byte) (x % 10 + '0');
                x /= 10;
            }
            ptr += n;

            return this;
        }

        public LightWriter2 ans(int x) {
            allocate(12);
            if (!breaked) buf[ptr++] = ' ';
            breaked = false;

            if (x < 0) {
                buf[ptr++] = '-';
                x = -x;
            }
            int n = countDigits(x);
            for (int i = ptr + n - 1; ptr <= i; i--) {
                buf[i] = (byte) (x % 10 + '0');
                x /= 10;
            }
            ptr += n;

            return this;
        }

        public LightWriter2 ans(Object obj) {
            return ans(Objects.toString(obj));
        }

        public LightWriter2 ln() {
            allocate(1);
            buf[ptr++] = '\n';
            breaked = true;
            if (autoflush) {
                try {
                    out.flush();
                } catch (IOException ex) {
                    throw new UncheckedIOException(ex);
                }
            }
            return this;
        }

        private static class WriterOutputStream extends OutputStream {
            final Writer writer;
            final CharsetDecoder decoder;

            WriterOutputStream(Writer writer) {
                this.writer = writer;
                this.decoder = StandardCharsets.UTF_8.newDecoder();
            }

            public void write(int b) throws IOException {
                writer.write(b);
            }

            public void write(byte[] b) throws IOException {
                writer.write(decoder.decode(ByteBuffer.wrap(b)).array());
            }

            public void write(byte[] b, int off, int len) throws IOException {
                writer.write(decoder.decode(ByteBuffer.wrap(b, off, len)).array());
            }

            public void flush() throws IOException {
                writer.flush();
            }

            public void close() throws IOException {
                writer.close();
            }

        }

    }

    static interface Verified {
    }

    static abstract class LightScannerAdapter implements AutoCloseable {
        public abstract String string();

        public long longs() {
            return Long.parseLong(string());
        }

        public final long[] longs(int length) {
            long[] res = new long[length];
            Arrays.setAll(res, ignored -> longs());
            return res;
        }

        public abstract void close();

    }

    static final class IntMath {
        private IntMath() {
        }

        public static Map<Long, Integer> primeFactorize(long p) {
            Map<Long, Integer> factor = new HashMap<>();
            if ((p & 1) == 0) {
                int c = 0;
                do {
                    c++;
                    p >>= 1;
                } while ((p & 1) == 0);
                factor.put(2L, c);
            }
            for (long i = 3; i * i <= p; i += 2) {
                if (p % i == 0) {
                    int c = 0;
                    do {
                        c++;
                        p /= i;
                    } while ((p % i) == 0);
                    factor.put(i, c);
                }
            }
            if (p > 1) {
                factor.put(p, 1);
            }
            return factor;
        }

    }

    static class HeapSort {
        private HeapSort() {
        }

        private static void heapfy(long[] a, int low, int high, int i, long val) {
            int child = 2 * i - low + 1;
            while (child < high) {
                if (child + 1 < high && a[child] < a[child + 1]) {
                    child++;
                }
                if (val >= a[child]) {
                    break;
                }
                a[i] = a[child];
                i = child;
                child = 2 * i - low + 1;
            }
            a[i] = val;
        }

        static void sort(long[] a, int low, int high) {
            for (int p = (high + low) / 2 - 1; p >= low; p--) {
                heapfy(a, low, high, p, a[p]);
            }
            while (high > low) {
                high--;
                long pval = a[high];
                a[high] = a[low];
                heapfy(a, low, high, low, pval);
            }
        }

    }

    static class IntroSort {
        private static int INSERTIONSORT_THRESHOLD = 16;

        private IntroSort() {
        }

        static void sort(long[] a, int low, int high, int maxDepth) {
            while (high - low > INSERTIONSORT_THRESHOLD) {
                if (maxDepth-- == 0) {
                    HeapSort.sort(a, low, high);
                    return;
                }
                int cut = QuickSort.step(a, low, high);
                sort(a, cut, high, maxDepth);
                high = cut;
            }
            InsertionSort.sort(a, low, high);
        }

        public static void sort(long[] a) {
            if (a.length <= INSERTIONSORT_THRESHOLD) {
                InsertionSort.sort(a, 0, a.length);
            } else {
                sort(a, 0, a.length, 2 * BitMath.msb(a.length));
            }
        }

    }

    static final class BitMath {
        private BitMath() {
        }

        public static int count(int v) {
            return Integer.bitCount(v);
        }

        public static int msb(int v) {
            if (v == 0) {
                throw new IllegalArgumentException("Bit not found");
            }
            v |= (v >> 1);
            v |= (v >> 2);
            v |= (v >> 4);
            v |= (v >> 8);
            v |= (v >> 16);
            return count(v) - 1;
        }

    }

    static final class ArrayUtil {
        private ArrayUtil() {
        }

        public static void swap(long[] a, int x, int y) {
            long t = a[x];
            a[x] = a[y];
            a[y] = t;
        }

    }
}