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.math.BigInteger;
import java.util.ArrayList;
import java.util.Scanner;
import java.util.TreeMap;

public class Main {
    static int n,k;
    public static void main(String[] args) {
        Scanner cin=new Scanner(System.in);
        n=cin.nextInt();k=cin.nextInt();
        TreeMap<Long, ArrayList<Long>>primes=new TreeMap<>();
        long [] a=new long[n];
        for (int i=0;i<n;i++){
            a[i]=cin.nextLong();
            BigInteger cur=new BigInteger(String.valueOf(a[i]));
            if (cur.isProbablePrime(20)){
                if (!primes.containsKey(a[i])){
                    primes.put(a[i],new ArrayList<>());
                }
                ArrayList<Long> now=primes.get(a[i]);
                now.add(a[i]);
                primes.put(a[i],now);
                a[i]=-1;
            }
            else {
                for (int j=2;j<=64;j++){
                    Long tmp=Math.round(Math.pow(a[i],1.0/j));
                    BigInteger x=new BigInteger(String.valueOf(tmp));
                    if(x.pow(j).compareTo(BigInteger.valueOf(a[i]))==0){
                        if (x.isProbablePrime(20)){
                            if (!primes.containsKey(tmp)){
                                primes.put(tmp,new ArrayList<>());
                            }
                            ArrayList<Long> now=primes.get(tmp);
                            now.add(a[i]);
                            primes.put(tmp,now);
                            a[i]=-1;
                            break;
                        }
                    }
                }
            }
        }
        int cnt=0,mx=0;
        long pos = 0;
        if (k==1){
            System.out.println(0);
            return;
        }
        ArrayList<Long> rr=new ArrayList<>();
        for (Long i:primes.keySet()){
            if (primes.get(i).size()==1){
                rr.add(i);
            }
            else {
                cnt+=primes.get(i).size();
                mx=Math.max(mx,primes.get(i).size());
            }
        }
        for (Long i:rr){
            primes.remove(i);
        }
        for (Long i:primes.keySet()){
            if (mx==primes.get(i).size()){
                pos=i;break;
            }
        }
        ArrayList<Long>[] ok=new ArrayList[n];
        int min=-1;
        for (int i=0;i<n;i++)ok[i]=new ArrayList<Long>();
        for (int i=0;i<n;i++){
            if (a[i]==-1)continue;
            long x=a[i];
            for (Long j:primes.keySet()){
                if (x%j==0){
                    x/=j;ok[i].add(j);
                    while (x%j==0)x/=j;
                }
            }
            if (x!=1){
                ok[i].clear();
                continue;
            }
            if (min==-1)min=i;
            else if (ok[i].size()<ok[min].size())min=i;
        }
        ArrayList<Long>ans=new ArrayList<>();
        if (cnt>=k){
            if (mx==2) {
                if (k % 2 != 0){
                    if (min!=-1){
                        ans.add(a[min]);k--;
                        for (Long i : ok[min]) {
                            ArrayList<Long> cur = primes.get(i);
                            ans.add(cur.get(0));
                            ans.add(cur.get(1));
                            cur.clear();
                            k -= 2;
                        }
                    }
                }
                tail(primes,ans);
            }
            else {
                for(Long i:primes.get(pos)){
                    ans.add(i);k--;
                    if (k==0)break;
                }
                primes.remove(pos);
//                System.out.println(ans);
//                System.out.println(k);
                if (k>0){
                    for (Long i:primes.keySet()){
                        if (k==0)break;
                        ArrayList<Long> cur=primes.get(i);
                        ans.add(cur.get(0));ans.add(cur.get(1));k-=2;
                        for (int j=2;j<cur.size()&&k>0;j++){
                            ans.add(cur.get(j));k--;
                        }
                        if (k<0){
                            ans.remove(0);
                            k++;
                        }
                    }
                }
//                System.out.println(ans);
//                System.out.println(k);
            }
        }
        else {
            for (Long i:primes.keySet()){
                ArrayList<Long> cur=primes.get(i);
                for (Long j:cur){
                    ans.add(j);
                    k--;
                }
            }
            for (int i=0;i<n&&k>0;i++){
                if (ok[i].size()!=0){
                    ans.add(a[i]);
                    k--;
                }
            }
        }
        if (k==0){
            for (Long i:ans){
                System.out.print(i);
                System.out.print(' ');
            }
        }
        else {
            System.out.print(0);
        }
    }
    private static void tail(TreeMap<Long, ArrayList<Long>> primes, ArrayList<Long> ans) {
        for (Long i:primes.keySet()){
            ArrayList<Long> cur=primes.get(i);
            for (int j=0;j+1<cur.size()&&k>0;j+=2,k-=2){
                ans.add(cur.get(j));
                ans.add(cur.get(j+1));
            }
        }
    }
}