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

Solution:
#include <bits/stdc++.h>
template <class T>
inline void read(T &x) {
  x = 0;
  register char c = getchar();
  register bool f = 0;
  while (!isdigit(c)) f ^= c == '-', c = getchar();
  while (isdigit(c)) x = x * 10 + c - '0', c = getchar();
  if (f) x = -x;
}
template <class T>
inline void print(T x) {
  if (x < 0) putchar('-'), x = -x;
  if (x > 9) print(x / 10);
  putchar(x % 10 + '0');
}
template <class T>
inline void print(T x, char c) {
  print(x), putchar(c);
}
template <class T>
inline T gcd(T n, T m) {
  return m ? gcd(m, n % m) : n;
}
template <const int N>
struct Prime : std::vector<int> {
  Prime() {
    std::vector<bool> vis(N);
    for (int i = 2; i < N; i++) {
      if (!vis[i]) this->push_back(i);
      for (int j : *this) {
        if (i * j >= N) break;
        vis[i * j] = true;
        if (!(i % j)) break;
      }
    }
  }
};
const int N = 1e5 + 10, M = 1e7 + 10;
int n, k, A, B, C, a[N], deg[N], v[N][8], l[N], f[M];
Prime<10000> prime;
std::vector<int> pos;
std::unordered_map<int, int> primeid;
void affect(int *v, int l, int x) {
  std::function<void(int, int)> dfs = [&](int i, int s) {
    if (i == l) {
      if (s != 1) f[s] += x;
      return;
    }
    dfs(i + 1, s);
    dfs(i + 1, s * v[i]);
  };
  dfs(0, 1);
}
int query(int *v, int l) {
  int res = 0;
  std::function<void(int, int)> dfs = [&](int i, int s) {
    if (i == l) {
      res += s < 0 ? -f[-s] : f[s];
      return;
    }
    dfs(i + 1, s);
    dfs(i + 1, s * -v[i]);
  };
  dfs(0, -1);
  return res;
}
int main() {
  read(n), read(k);
  for (int i = 1; i <= n; i++) read(a[i]);
  for (int i = 0; i < prime.size(); i++) primeid[prime[i]] = i;
  for (int x, i = 1; i <= n; i++) {
    x = a[i];
    for (int j = 0; prime[j] * prime[j] <= x; j++)
      if (x % prime[j] == 0) {
        v[i][l[i]++] = prime[j];
        while (x % prime[j] == 0) x /= prime[j];
      }
    if (x != 1) v[i][l[i]++] = x;
  }
  for (int i = 1; i <= n; i++) affect(v[i], l[i], 1);
  for (int i = 1; i <= n; i++) deg[i] = query(v[i], l[i]) - 1;
  for (int i = 1; i <= n; i++) affect(v[i], l[i], -1);
  int fulldeg = 0;
  for (int i = 1; i <= n; i++) fulldeg += deg[i] == n - 1;
  if (fulldeg >= k) {
    for (int i = 1; i <= n; i++)
      if (deg[i] == n - 1) pos.push_back(i);
  } else {
    for (int i = 1; i <= n; i++)
      if (n - 1 - deg[i] >= 2) {
        A = i;
        for (int j = 1; j <= n; j++)
          if (j != A && gcd(a[i], a[j]) == 1) {
            if (!B) {
              B = j;
              continue;
            }
            if (!C) {
              C = j;
              continue;
            }
            break;
          }
        break;
      }
    if (A) {
      if (!(B && C))
        printf("Assert: Passing [%s] in LINE %d\n", __FUNCTION__, 120), exit(0);
      auto getp = [&](int cur) {
        std::vector<int> res;
        for (int i = 1; i <= n && res.size() < cur; i++)
          if (i != A && i != B && i != C) {
            res.push_back(i);
          }
        return res;
      };
      auto solve = [&](int cur) {
        int res = 0;
        std::vector<int> p = getp(cur);
        for (int i : p) affect(v[i], l[i], 1);
        for (int i : p) deg[i] = query(v[i], l[i]) - 1;
        for (int i : p) affect(v[i], l[i], -1);
        for (int i : p) res += deg[i] != cur - 1;
        return res;
      };
      int l = 1, r = n - 3, mid, res = -1;
      while (l <= r) {
        mid = (l + r) >> 1;
        solve(mid) + 3 >= k ? (res = mid, r = mid - 1) : (l = mid + 1);
      }
      if (!(~res))
        printf("Assert: Passing [%s] in LINE %d\n", __FUNCTION__, 144), exit(0);
      int now = solve(res);
      std::vector<int> p = getp(res);
      for (int i : p)
        if (deg[i] != res - 1) pos.push_back(i);
      if (pos.size() < k) pos.push_back(A);
      if (pos.size() < k) pos.push_back(B);
      if (pos.size() < k) pos.push_back(C);
    } else {
      uint64_t all = 0;
      std::vector<int> match(n + 1);
      std::vector<uint64_t> hsh(n + 1);
      std::map<uint64_t, int> map;
      std::map<int, uint64_t> sta;
      std::mt19937_64 rng(
          20040725 ^
          std::chrono::steady_clock::now().time_since_epoch().count());
      for (int i = 1; i <= n; i++)
        hsh[i] = rng(), all ^= hsh[i], map[hsh[i]] = i;
      for (int i = 1; i <= n; i++)
        for (int x = 1; x < (1 << l[i]); x++) {
          int s = 1;
          for (int j = 0; j < l[i]; j++)
            if ((x >> j) & 1) s *= v[i][j];
          sta[s] ^= hsh[i];
        }
      for (int i = 1; i <= n; i++)
        if (deg[i] == n - 2) {
          uint64_t tem = all;
          for (int x = 1; x < (1 << l[i]); x++) {
            int s = 1;
            for (int j = 0; j < l[i]; j++)
              if ((x >> j) & 1) s *= v[i][j];
            tem ^= sta[s];
          }
          match[i] = map[tem];
        }
      for (int i = 1; i <= n; i++)
        if (!match[i] || i < match[i]) pos.push_back(i);
    }
  }
  if (!(pos.size() >= k))
    printf("Assert: Passing [%s] in LINE %d\n", __FUNCTION__, 186), exit(0);
  for (int i = 0; i < k; i++) print(pos[i], " \n"[i + 1 == k]);
}