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 namespace std;
const int maxn = 1e5 + 10, Max = 1e7 + 10;
template <typename A, typename B>
ostream& operator<<(ostream& out, pair<A, B> p) {
  out << "{ " << p.first << ", " << p.second << " }";
  return out;
}
template <typename T>
ostream& operator<<(ostream& out, vector<T> v) {
  out << "[ ";
  for (int i = 0; i < int((v).size()); i++) {
    out << v[i];
    if (i != int((v).size()) - 1) out << " ,";
  }
  out << " ]";
  return out;
}
int a[maxn], b[maxn], c[maxn], L[maxn], R[maxn];
vector<int> dv[maxn], v[maxn];
int bigp[Max], val[Max];
int zr[maxn];
void add(vector<int>& vec) {
  zr[0] = 1;
  val[1]++;
  for (int msk = 1; msk < (1 << int((vec).size())); msk++)
    zr[msk] = zr[msk ^ (msk & -msk)] * vec[__builtin_ctz(msk)], val[zr[msk]]++;
}
int ask(vector<int>& vec) {
  zr[0] = 1;
  int ans = val[1];
  for (int msk = 1; msk < (1 << int((vec).size())); msk++)
    zr[msk] = zr[msk ^ (msk & -msk)] * vec[__builtin_ctz(msk)],
    ans += (__builtin_popcount(msk) & 1 ? -1 : 1) * val[zr[msk]];
  return ans;
}
void go(int N) {
  for (int i = 0; i < N; i++) {
    L[i] = 0, R[i] = N + 1;
    dv[i].clear();
    int tmp = b[i];
    while (tmp > 1) {
      dv[i].push_back(bigp[tmp]);
      tmp /= bigp[tmp];
    }
  }
  while (true) {
    vector<pair<int, int> > vec;
    for (int i = 0; i < N; i++) {
      if (R[i] - L[i] > 1) vec.push_back({(R[i] + L[i]) >> 1, i});
    }
    if (int((vec).size()) == 0) break;
    memset(val, 0, sizeof val);
    sort(vec.begin(), vec.end());
    int pt = 0;
    for (int i = 0; i < N; i++) {
      if (pt == int((vec).size())) break;
      add(dv[i]);
      while (pt < int((vec).size()) && vec[pt].first == i + 1) {
        if (ask(dv[vec[pt].second]) == 0)
          L[vec[pt].second] = (L[vec[pt].second] + R[vec[pt].second]) >> 1;
        else
          R[vec[pt].second] = (L[vec[pt].second] + R[vec[pt].second]) >> 1;
        pt++;
      }
    }
  }
  for (int i = 0; i < N; i++) {
    if (L[i] < N) v[c[i]].push_back(c[L[i]]), v[c[L[i]]].push_back(c[i]);
  }
}
bool mark[maxn];
int SZ[maxn];
vector<int> ids[maxn];
map<int, vector<int> > poses;
void dfs(int u) {
  mark[u] = 1;
  SZ[u] = 1;
  for (int y : v[u])
    if (mark[y] == 0) dfs(y), SZ[u] += SZ[y];
}
void dfs2(int u, int& k, vector<int>& vans) {
  while (k > 0 && int((ids[u]).size())) {
    --k;
    vans.push_back(ids[u].back());
    ids[u].pop_back();
  }
  if (k == 0) return;
  mark[u] = 1;
  for (int y : v[u])
    if (mark[y] == 0) dfs2(y, k, vans);
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie();
  for (int i = 2; i < Max; i++) {
    if (bigp[i] == 0)
      for (int j = i; j < Max; j += i) bigp[j] = i;
  }
  int n, k;
  cin >> n >> k;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    int tmp = a[i];
    a[i] = 1;
    while (tmp > 1) {
      int P = bigp[tmp];
      a[i] *= P;
      while (tmp % P == 0) tmp /= P;
    }
    poses[a[i]].push_back(i);
  }
  sort(a, a + n);
  n = unique(a, a + n) - a;
  for (int i = 0; i < n; i++) {
    ids[i] = poses[a[i]];
  }
  for (int i = 0; i < n; i++) {
    b[i] = a[i];
    c[i] = i;
  }
  int ID = -1;
  for (int i = 0; i < n; i++) {
    if (b[i] == 1) ID = i;
  }
  if (ID != -1) {
    vector<int> ans;
    for (int x : ids[ID]) ans.push_back(x);
    for (int i = 0; i < n; i++)
      if (i != ID)
        for (int x : ids[i]) ans.push_back(x);
    for (int i = 0; i < k; i++) cout << ans[i] + 1 << " ";
    return cout << endl, 0;
  }
  go(n);
  vector<int> vec;
  for (int i = 0; i < n; i++) {
    if (mark[i] == 0 &&
        (int((v[i]).size()) == 0 ||
         int((ids[v[i].back()]).size()) <= int((ids[i]).size())))
      dfs(i), vec.push_back(i);
  }
  sort(vec.begin(), vec.end(), [&](int i, int j) { return SZ[i] < SZ[j]; });
  int num = 0, num2 = 0;
  while (num < int((vec).size()) && SZ[vec[num]] == 1)
    num2 += int((ids[vec[num]]).size()), num++;
  if (num2 >= k) {
    vector<int> ans;
    for (int i = 0; i < num; i++)
      for (int x : ids[vec[i]]) ans.push_back(x);
    for (int i = 0; i < k; i++) cout << ans[i] + 1 << " ";
    return cout << endl, 0;
  }
  for (int i = num; i < int((vec).size()); i++) {
    b[i - num] = a[vec[i]];
    c[i - num] = vec[i];
  }
  if (SZ[vec.back()] == 2) {
    go(int((vec).size()) - num);
    memset(mark, 0, sizeof mark);
    vec.clear();
    for (int i = 0; i < n; i++) {
      if (mark[i] == 0) dfs(i), vec.push_back(i);
    }
    sort(vec.begin(), vec.end(), [&](int i, int j) { return SZ[i] < SZ[j]; });
  }
  if (SZ[vec.back()] == 2) {
    vector<int> ans;
    for (int i = 0; i < int((vec).size()); i++)
      for (int x : ids[vec[i]]) ans.push_back(x);
    for (int i = 0; i < k; i++) cout << ans[i] + 1 << " ";
    return cout << endl, 0;
  }
  memset(mark, 0, sizeof mark);
  int lst = -1;
  vector<int> vans;
  dfs2(vec.back(), k, vans);
  lst = vans.back();
  for (int i = int((vec).size()) - 2; i >= 0; i--) {
    if (k == 1) {
      vans.erase(find(vans.begin(), vans.end(), lst));
      vans.push_back(ids[vec[i]][0]);
      vans.push_back(ids[v[vec[i]].back()][0]);
      k = 0;
    }
    dfs2(vec[i], k, vans);
  }
  for (int x : vans) cout << x + 1 << " ";
  return cout << endl, 0;
}