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>
using std::max;
using std::min;
const int inf = 0x3f3f3f3f, Inf = 0x7fffffff;
const long long INF = 0x3f3f3f3f3f3f3f3f;
__inline__ __attribute__((always_inline)) unsigned int rnd() {
  static unsigned int seed = 416;
  return seed ^= seed >> 5, seed ^= seed << 17, seed ^= seed >> 13;
}
template <typename _Tp>
_Tp gcd(const _Tp &a, const _Tp &b) {
  return (!b) ? a : gcd(b, a % b);
}
template <typename _Tp>
__inline__ __attribute__((always_inline)) _Tp abs(const _Tp &a) {
  return a >= 0 ? a : -a;
}
template <typename _Tp>
__inline__ __attribute__((always_inline)) void chmax(_Tp &a, const _Tp &b) {
  (a < b) && (a = b);
}
template <typename _Tp>
__inline__ __attribute__((always_inline)) void chmin(_Tp &a, const _Tp &b) {
  (b < a) && (a = b);
}
template <typename _Tp>
__inline__ __attribute__((always_inline)) void read(_Tp &x) {
  char ch(getchar());
  bool f(false);
  while (!isdigit(ch)) f |= ch == 45, ch = getchar();
  x = ch & 15, ch = getchar();
  while (isdigit(ch)) x = (((x << 2) + x) << 1) + (ch & 15), ch = getchar();
  f && (x = -x);
}
template <typename _Tp, typename... Args>
__inline__ __attribute__((always_inline)) void read(_Tp &t, Args &...args) {
  read(t);
  read(args...);
}
template <typename _Tp, typename... Args>
__inline__ __attribute__((always_inline)) _Tp min(const _Tp &a, const _Tp &b,
                                                  const Args &...args) {
  return a < b ? min(a, args...) : min(b, args...);
}
template <typename _Tp, typename... Args>
__inline__ __attribute__((always_inline)) _Tp max(const _Tp &a, const _Tp &b,
                                                  const Args &...args) {
  return a < b ? max(b, args...) : max(a, args...);
}
__inline__ __attribute__((always_inline)) int read_str(char *s) {
  char ch(getchar());
  while (ch == ' ' || ch == '\r' || ch == '\n') ch = getchar();
  char *tar = s;
  *tar = ch, ch = getchar();
  while (ch != ' ' && ch != '\r' && ch != '\n' && ch != EOF)
    *(++tar) = ch, ch = getchar();
  return tar - s + 1;
}
const int N = 100005;
const int MAXN = 10000005;
bool pr[MAXN];
int _p[MAXN >> 3], _pos;
int md[MAXN];
void sieve() {
  for (int i = 2; i < MAXN; ++i) {
    if (!pr[i]) {
      _p[++_pos] = i;
      md[i] = i;
    }
    for (int j = 1; j <= _pos && i * _p[j] < MAXN; ++j) {
      pr[i * _p[j]] = true;
      md[i * _p[j]] = _p[j];
      if (!(i % _p[j])) break;
    }
  }
}
std::vector<int> p[N], d[N];
int c[MAXN], cnt[1 << 8], mul[1 << 8];
int calc(int id) {
  int siz = ((int)p[id].size()), ans = 0;
  for (int i = 0; i < siz; ++i) mul[1 << i] = p[id][i];
  for (int i = 1; i < 1 << siz; ++i) {
    cnt[i] = cnt[i >> 1] + (i & 1);
    mul[i] = mul[i ^ ((i) & (-(i)))] * mul[((i) & (-(i)))];
    if (cnt[i] & 1)
      ans += c[mul[i]];
    else
      ans -= c[mul[i]];
  }
  return ans;
}
int a[N];
int _val[11], _cnt[11], pos, cur_id;
void dfs(int dep, int val) {
  if (dep == pos + 1) {
    d[cur_id].push_back(val);
    return;
  }
  for (int i = 0; i <= _cnt[dep]; ++i) {
    dfs(dep + 1, val);
    if (i < _cnt[dep]) val *= _val[dep];
  }
}
bool ban[N], vis[N];
int deg[N];
int f(int mid) {
  while (ban[mid]) --mid;
  if (!mid) return false;
  int qwq = 0;
  for (int i = 1; i <= mid; ++i)
    if (!ban[i]) {
      ++qwq;
      for (auto it : d[i]) ++c[it];
    }
  int ans = 0;
  for (int i = 1; i <= mid; ++i)
    if (!ban[i] && calc(i) != qwq) ++ans;
  for (int i = 1; i <= mid; ++i)
    if (!ban[i])
      for (auto it : d[i]) --c[it];
  return ans;
}
std::vector<int> getnodes(int mid) {
  while (ban[mid]) --mid;
  std::vector<int> nd;
  int qwq = 0;
  for (int i = 1; i <= mid; ++i)
    if (!ban[i]) {
      ++qwq;
      for (auto it : d[i]) ++c[it];
    }
  for (int i = 1; i <= mid; ++i)
    if (!ban[i] && calc(i) != qwq) nd.push_back(i);
  for (int i = 1; i <= mid; ++i)
    if (!ban[i])
      for (auto it : d[i]) --c[it];
  return nd;
}
int main() {
  mul[0] = 1;
  sieve();
  int n, k;
  read(n, k);
  for (int i = 1; i <= n; ++i) {
    read(a[i]);
    ++c[a[i]];
    int cur = a[i], last = 0;
    pos = 0;
    while (cur > 1) {
      if (md[cur] != last)
        p[i].push_back(md[cur]), _val[++pos] = md[cur], _cnt[pos] = 1;
      else
        ++_cnt[pos];
      last = md[cur];
      cur /= last;
    }
    cur_id = i;
    dfs(1, 1);
  }
  for (int j = 1; j <= _pos; ++j)
    for (int i = (MAXN - 1) / _p[j]; i >= 1; --i) c[i] += c[i * _p[j]];
  std::vector<int> nd;
  for (int i = 1; i <= n; ++i) {
    if ((deg[i] = calc(i)) <= n - 2) {
      nd.push_back(i);
      for (int j = 1; j <= n && ((int)nd.size()) < 3; ++j)
        if (i != j && gcd(a[i], a[j]) == 1) nd.push_back(j);
      break;
    }
  }
  if (nd.empty()) {
    std::vector<int> clique, rest;
    for (int i = 1; i <= n; ++i)
      if (deg[i] == n)
        clique.push_back(i);
      else
        rest.push_back(i);
    if (((int)clique.size()) > k) clique.resize(k);
    for (int i = 1; i <= n && ((int)clique.size()) < k; ++i) {
      if (!vis[i] && deg[i] == n - 1) {
        clique.push_back(i);
        for (auto it : rest)
          if (gcd(a[it], a[i]) == 1) vis[it] = true;
      }
    }
    for (auto it : clique) printf("%d ", it);
    printf("\n");
    return 0;
  }
  assert(((int)nd.size()) == 3);
  if (k == 3) {
    for (auto it : nd) printf("%d ", it);
    printf("\n");
    return 0;
  }
  for (auto it : nd) ban[it] = true;
  for (auto id : nd)
    for (auto it : d[id]) --c[it];
  std::vector<int> clique;
  for (int i = 1; i <= n; ++i)
    if (!ban[i] && ((deg[i] = calc(i)) == n - 3)) clique.push_back(i);
  if (((int)clique.size()) >= k) {
    clique.resize(k);
    for (auto it : clique) printf("%d ", it);
    printf("\n");
    return 0;
  }
  memset(c, 0, sizeof(c));
  int l = 1, r = n;
  while (l < r) {
    int mid = (l + r) >> 1;
    if (f(mid) + 3 >= k)
      r = mid;
    else
      l = mid + 1;
  }
  std::vector<int> v1 = getnodes(l - 1);
  std::vector<int> v2 = getnodes(l);
  assert(f(l - 1) == ((int)v1.size()));
  assert(f(l) == ((int)v2.size()));
  assert(((int)v1.size()) + 3 < k);
  assert(((int)v2.size()) + 3 >= k);
  std::sort(v1.begin(), v1.end());
  std::vector<int> qwq;
  for (auto it : v2) {
    auto _ = std::lower_bound(v1.begin(), v1.end(), it);
    if (_ == v1.end() || *_ != it) qwq.push_back(it);
  }
  std::sort(qwq.begin(), qwq.end());
  assert(((int)v1.size()) + ((int)qwq.size()) == ((int)v2.size()));
  if (((int)v1.size()) + 3 + 1 == k && ((int)qwq.size()) != 1)
    v1.push_back(nd[0]), v1.push_back(nd[1]);
  else
    v1.push_back(nd[0]), v1.push_back(nd[1]), v1.push_back(nd[2]);
  while (((int)v1.size()) < k) {
    v1.push_back(qwq.back());
    qwq.pop_back();
  }
  assert(((int)v1.size()) == k);
  for (auto it : v1) printf("%d ", it);
  printf("\n");
  return 0;
}