Problem: Consider an undirected graph G with n vertices. There is a value a_i in each vertex.

Two vertices i and j are connected with an edge if and only if gcd(a_i, a_j) > 1, where gcd(x, y) denotes the [greatest common divisor (GCD)](https://en.wikipedia.org/wiki/Greatest_common_divisor) of integers x and y.

Consider a set of vertices. Let's call a vertex in this set fair if it is connected with an edge with all other vertices in this set.

You need to find a set of k vertices (where k is a given integer, 2 ⋅ k ≤ n) where all vertices are fair or all vertices are not fair. One can show that such a set always exists.

Input

The first line contains integers n and k (6 ≤ 2 ⋅ k ≤ n ≤ 10^5) — the number of vertices and parameter k.

The second line contains n integers a_1, a_2, …, a_n (2 ≤ a_i ≤ 10^7) — the values in the vertices.

Output

Print exactly k distinct integers — the indices of the vertices in the chosen set in any order.

Examples

Input


6 3
6 15 10 8 14 12


Output


2 4 5

Input


8 4
11 15 10 6 21 15 10 6


Output


5 7 1 2

Input


10 5
3003 17017 3230 49742 546 41990 17765 570 21945 36465


Output


1 2 4 5 6

Note

In the first test case, set \{2, 4, 5\} is an example of set where no vertices are fair. The vertex 2 does not share an edge with vertex 4 since gcd(15, 8) = 1. The vertex 4 does not share an edge with vertex 2. The vertex 5 does not share an edge with vertex 2.

In the second test case, set \{8, 5, 6, 4\} is an example of a set where all vertices are fair.

Solution (in JAVA):

Solution:
import java.io.*;
import java.lang.reflect.Array;
import java.util.*;

public class Test {

    static int readInt() {
        int ans = 0;
        boolean neg = false;
        try {
            boolean start = false;
            for (int c = 0; (c = System.in.read()) != -1; ) {
                if (c == '-') {
                    start = true;
                    neg = true;
                    continue;
                } else if (c >= '0' && c <= '9') {
                    start = true;
                    ans = ans * 10 + c - '0';
                } else if (start) break;
            }
        } catch (IOException e) {
        }
        return neg ? -ans : ans;
    }

    static long readLong() {
        long ans = 0;
        boolean neg = false;
        try {
            boolean start = false;
            for (int c = 0; (c = System.in.read()) != -1; ) {
                if (c == '-') {
                    start = true;
                    neg = true;
                    continue;
                } else if (c >= '0' && c <= '9') {
                    start = true;
                    ans = ans * 10 + c - '0';
                } else if (start) break;
            }
        } catch (IOException e) {
        }
        return neg ? -ans : ans;
    }

    static String readLine() {
        StringBuilder b = new StringBuilder();
        try {
            boolean start = false;
            for (int c = 0; (c = System.in.read()) != -1; ) {
                if (c != '\r' && c != '\n') {
                    start = true;
                    b.append((char)c);
                } else if (start) break;
            }
        } catch (IOException e) {
        }
        return b.toString();
    }

    static PrintWriter writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));

    void start() {
        int n = readInt(), k = readInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) a[i] = readInt();

        int N = 10_000_001;
        int[] prev = new int[N];
        for (int i = 0; i < N; i++) prev[i] = i;
        for (int i = 2; i < 3400; i++)
            if (prev[i] == i)
                for (int j = i + i; j < N; j += i) if (prev[j] == j) prev[j] = i;

        List<Integer>[] facts = new List[n];
        for (int i = 0; i < n; i++) facts[i] = new ArrayList<>();

        int pcnt = 0;
        int[] pid = new int[N];
        Arrays.fill(pid, -1);
        for (int i = 0; i < n; i++) {
            int j = a[i];
            while (j > 1) {
                int p = prev[j];
                while (j % p == 0) j /= p;
                if (pid[p] == -1) pid[p] = pcnt++;
                facts[i].add(pid[p]);
            }
        }

        List<Integer>[] ids = new List[pcnt];
        for (int i = 0; i < pcnt; i++) ids[i] = new ArrayList<>();
        for (int i = 0; i < n; i++)
            for (int f : facts[i]) ids[f].add(i);
        BitSet[] has = new BitSet[pcnt];
        for (int i = 0; i < pcnt; i++)
            if (ids[i].size() > n / 300) {
                has[i] = new BitSet(n);
                for (int j : ids[i]) has[i].set(j);
            }

        List<Integer> alone = new ArrayList<>();
        BitSet alive = new BitSet(n);
        for (int i = 0; i < n; i++) alive.set(i);
        boolean[] visited = new boolean[N];
        List<List<Integer>> comp = new ArrayList<>();
        int[] q = new int[n];
        BitSet go = new BitSet(n);
        for (int i = 0; i < n; i++) {
            if (!alive.get(i)) continue;
            alive.clear(i);
            int rr = 0;
            q[rr++] = i;
            for (int j = 0; j < rr; j++) {
                int u = q[j];
                int v = a[u];
                if (visited[v]) continue;
                visited[v] = true;
                go.clear();
                go.or(alive);
                for (int f : facts[u]) {
                    if (has[f] == null)
                        for (int x : ids[f]) go.clear(x);
                    else go.andNot(has[f]);
                }
                for (int x = go.nextSetBit(0); x >= 0; x = go.nextSetBit(x+1)) {
                    q[rr++] = x;
                    alive.clear(x);
                }
            }
            if (rr == 1) alone.add(i);
            else {
                List<Integer> cs = new ArrayList<>();
                for (int x = 0; x < rr; x++) cs.add(q[x]);
                comp.add(cs);
            }
        }
        if (alone.size() + comp.size() >= k) {
            for (int i = 0; i < alone.size() && k > 0; i++) {
                writer.print((alone.get(i) + 1) + " ");
                k--;
            }
            for (int i = 0; i < comp.size() && k > 0; i++) {
                writer.print((comp.get(i).get(0) + 1) + " ");
                k--;
            }
            return;
        }
        Collections.sort(comp, (x, y) -> Integer.compare(y.size(), x.size()));
        int sum = 0;
        for (int i = 0; i < comp.size() && sum < k - 1; i++) sum += comp.get(i).size();
        if (sum == k - 1) comp.get(0).remove(comp.get(0).size() - 1);
        loop:
        for (List<Integer> list : comp)
            for (int v : list) {
                writer.print((v + 1) + " ");
                k--;
                if (k == 0) break loop;
            }
    }

    public static void main(String[] args) {
        Test te = new Test();
        te.start();
        writer.flush();
    }
}