#include <bits/stdc++.h>
using namespace std;
int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};
const double PI = acos(-1.0);
template <class T>
void debug(T a, T b) {
  for (T i = a; i != b; ++i) cout << *i << " ";
  cout << endl;
}
template <class T>
void chmin(T& a, const T& b) {
  if (a > b) a = b;
}
template <class T>
void chmax(T& a, const T& b) {
  if (a < b) a = b;
}
int n, k;
pair<int, int> p[1005];
int dist[1005][1005];
int zip[1000005];
int es[1000005], nxt[1000005], head[1005];
int deg[1005], mark[1005];
int m;
pair<int, int> order[1005];
int used[1005];
int dfs(int ind, int k) {
  if (k < 0) return 0;
  while (ind < n && order[ind].first != -1 && mark[order[ind].second]) ++ind;
  if (ind == n || order[ind].first == -1) {
    return 1;
  }
  int v = order[ind].second;
  {
    int kk = k;
    for (int i = head[v]; i != -1; i = nxt[i]) {
      int to = es[i];
      if (mark[to] == 0) {
        --kk;
        mark[to] = v + 1;
        used[to] = 1;
      }
    }
    if (dfs(ind + 1, kk)) {
      used[v] = 0;
      return 1;
    }
    for (int i = head[v]; i != -1; i = nxt[i]) {
      int to = es[i];
      if (mark[to] == v + 1) {
        mark[to] = 0;
        used[to] = 0;
      }
    }
  }
  if (deg[v] > 1) {
    mark[v] = v + 1;
    if (dfs(ind + 1, k - 1)) {
      used[v] = 1;
      return 1;
    }
    mark[v] = 0;
  }
  return 0;
}
bool cmp(const pair<int, int>& a, const pair<int, int>& b) {
  if (a.first == 0 || a.first == 1) return true;
  if (b.first == 0 || b.first == 1) return false;
  if (a.first == -1) return false;
  if (b.first == -1) return true;
  return a.first < b.first;
}
bool check() {
  memset(used, 0, sizeof(used));
  memset(mark, 0, sizeof(mark));
  for (int i = 0; i < (int)n; ++i)
    if (deg[i] > k) mark[i] = -1;
  int k2 = k;
  int m2 = m / 2;
  for (int i = 0; i < (int)n; ++i)
    if (mark[i]) {
      --k2;
      used[i] = 1;
      for (int j = head[i]; j != -1; j = nxt[j]) --deg[es[j]], --m2;
    }
  if (m2 > k2 * k2 || k2 < 0) return false;
  for (int i = 0; i < (int)n; ++i)
    if (!mark[i]) {
      while (head[i] != -1 && mark[es[head[i]]]) head[i] = nxt[head[i]];
      for (int j = head[i]; j != -1; j = nxt[j]) {
        int nx = nxt[j];
        while (nx != -1 && mark[es[nx]]) nx = nxt[nx];
        nxt[j] = nx;
      }
    }
  memset(deg, 0, sizeof(deg));
  for (int i = 0; i < (int)n; ++i) order[i] = make_pair(-1, -1);
  for (int i = 0; i < (int)n; ++i)
    if (!mark[i]) {
      for (int j = head[i]; j != -1; j = nxt[j], ++deg[i])
        ;
      order[i] = make_pair(deg[i], i);
    }
  sort(order, order + n, greater<pair<int, int> >());
  return dfs(0, k2);
}
int res[1005];
int main() {
  scanf("%d%d", &n, &k);
  for (int i = 0; i < (int)n; ++i) scanf("%d%d", &p[i].first, &p[i].second);
  int cnt = 0;
  for (int i = 0; i < (int)n; ++i)
    for (int j = 0; j < (int)n; ++j)
      dist[i][j] = ((p[i].first - p[j].first) * (p[i].first - p[j].first)) +
                   ((p[i].second - p[j].second) * (p[i].second - p[j].second)),
      zip[cnt++] = dist[i][j];
  sort(zip, zip + cnt, greater<int>());
  int zn = unique(zip, zip + cnt) - zip;
  zip[zn] = 0;
  int lb = -1, ub = zn;
  while (ub - lb > 1) {
    int md = (ub + lb) >> 1, len = zip[md];
    m = 0;
    memset(deg, 0, sizeof(deg));
    memset(head, -1, sizeof(head));
    for (int i = 0; i < (int)n; ++i)
      for (int j = 0; j < (int)i; ++j)
        if (dist[i][j] >= len) {
          es[m] = j;
          nxt[m] = head[i];
          head[i] = m++;
          es[m] = i;
          nxt[m] = head[j];
          head[j] = m++;
          ++deg[i];
          ++deg[j];
        }
    if (check()) {
      lb = md;
      memcpy(res, used, sizeof(res));
    } else
      ub = md;
  }
  vector<int> res2;
  for (int i = 0; i < (int)n; ++i)
    if (res[i]) res2.push_back(i);
  for (int i = 0; i < (int)n; ++i)
    if (!res[i] && res2.size() < k) res2.push_back(i);
  for (int i = 0; i < (int)k; ++i)
    printf("%d%c", res2[i] + 1, i == k - 1 ? '\n' : ' ');
  return 0;
}

### Prompt

Your task is to create a cpp solution to the following problem:

You are given n points on the plane. You need to delete exactly k of them (k < n) so that the diameter of the set of the remaining n - k points were as small as possible. The diameter of a set of points is the maximum pairwise distance between the points of the set. The diameter of a one point set equals zero.

Input

The first input line contains a pair of integers n, k (2 ≤ n ≤ 1000, 1 ≤ k ≤ 30, k < n) — the numbers of points on the plane and the number of points to delete, correspondingly.

Next n lines describe the points, one per line. Each description consists of a pair of integers xi, yi (0 ≤ xi, yi ≤ 32000) — the coordinates of the i-th point. The given points can coincide.

Output

Print k different space-separated integers from 1 to n — the numbers of points to delete. The points are numbered in the order, in which they are given in the input from 1 to n. You can print the numbers in any order. If there are multiple solutions, print any of them.

Examples

Input

5 2
1 2
0 0
2 2
1 1
3 3


Output

5 2

Input

4 1
0 0
0 0
1 1
1 1


Output

3

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};
const double PI = acos(-1.0);
template <class T>
void debug(T a, T b) {
  for (T i = a; i != b; ++i) cout << *i << " ";
  cout << endl;
}
template <class T>
void chmin(T& a, const T& b) {
  if (a > b) a = b;
}
template <class T>
void chmax(T& a, const T& b) {
  if (a < b) a = b;
}
int n, k;
pair<int, int> p[1005];
int dist[1005][1005];
int zip[1000005];
int es[1000005], nxt[1000005], head[1005];
int deg[1005], mark[1005];
int m;
pair<int, int> order[1005];
int used[1005];
int dfs(int ind, int k) {
  if (k < 0) return 0;
  while (ind < n && order[ind].first != -1 && mark[order[ind].second]) ++ind;
  if (ind == n || order[ind].first == -1) {
    return 1;
  }
  int v = order[ind].second;
  {
    int kk = k;
    for (int i = head[v]; i != -1; i = nxt[i]) {
      int to = es[i];
      if (mark[to] == 0) {
        --kk;
        mark[to] = v + 1;
        used[to] = 1;
      }
    }
    if (dfs(ind + 1, kk)) {
      used[v] = 0;
      return 1;
    }
    for (int i = head[v]; i != -1; i = nxt[i]) {
      int to = es[i];
      if (mark[to] == v + 1) {
        mark[to] = 0;
        used[to] = 0;
      }
    }
  }
  if (deg[v] > 1) {
    mark[v] = v + 1;
    if (dfs(ind + 1, k - 1)) {
      used[v] = 1;
      return 1;
    }
    mark[v] = 0;
  }
  return 0;
}
bool cmp(const pair<int, int>& a, const pair<int, int>& b) {
  if (a.first == 0 || a.first == 1) return true;
  if (b.first == 0 || b.first == 1) return false;
  if (a.first == -1) return false;
  if (b.first == -1) return true;
  return a.first < b.first;
}
bool check() {
  memset(used, 0, sizeof(used));
  memset(mark, 0, sizeof(mark));
  for (int i = 0; i < (int)n; ++i)
    if (deg[i] > k) mark[i] = -1;
  int k2 = k;
  int m2 = m / 2;
  for (int i = 0; i < (int)n; ++i)
    if (mark[i]) {
      --k2;
      used[i] = 1;
      for (int j = head[i]; j != -1; j = nxt[j]) --deg[es[j]], --m2;
    }
  if (m2 > k2 * k2 || k2 < 0) return false;
  for (int i = 0; i < (int)n; ++i)
    if (!mark[i]) {
      while (head[i] != -1 && mark[es[head[i]]]) head[i] = nxt[head[i]];
      for (int j = head[i]; j != -1; j = nxt[j]) {
        int nx = nxt[j];
        while (nx != -1 && mark[es[nx]]) nx = nxt[nx];
        nxt[j] = nx;
      }
    }
  memset(deg, 0, sizeof(deg));
  for (int i = 0; i < (int)n; ++i) order[i] = make_pair(-1, -1);
  for (int i = 0; i < (int)n; ++i)
    if (!mark[i]) {
      for (int j = head[i]; j != -1; j = nxt[j], ++deg[i])
        ;
      order[i] = make_pair(deg[i], i);
    }
  sort(order, order + n, greater<pair<int, int> >());
  return dfs(0, k2);
}
int res[1005];
int main() {
  scanf("%d%d", &n, &k);
  for (int i = 0; i < (int)n; ++i) scanf("%d%d", &p[i].first, &p[i].second);
  int cnt = 0;
  for (int i = 0; i < (int)n; ++i)
    for (int j = 0; j < (int)n; ++j)
      dist[i][j] = ((p[i].first - p[j].first) * (p[i].first - p[j].first)) +
                   ((p[i].second - p[j].second) * (p[i].second - p[j].second)),
      zip[cnt++] = dist[i][j];
  sort(zip, zip + cnt, greater<int>());
  int zn = unique(zip, zip + cnt) - zip;
  zip[zn] = 0;
  int lb = -1, ub = zn;
  while (ub - lb > 1) {
    int md = (ub + lb) >> 1, len = zip[md];
    m = 0;
    memset(deg, 0, sizeof(deg));
    memset(head, -1, sizeof(head));
    for (int i = 0; i < (int)n; ++i)
      for (int j = 0; j < (int)i; ++j)
        if (dist[i][j] >= len) {
          es[m] = j;
          nxt[m] = head[i];
          head[i] = m++;
          es[m] = i;
          nxt[m] = head[j];
          head[j] = m++;
          ++deg[i];
          ++deg[j];
        }
    if (check()) {
      lb = md;
      memcpy(res, used, sizeof(res));
    } else
      ub = md;
  }
  vector<int> res2;
  for (int i = 0; i < (int)n; ++i)
    if (res[i]) res2.push_back(i);
  for (int i = 0; i < (int)n; ++i)
    if (!res[i] && res2.size() < k) res2.push_back(i);
  for (int i = 0; i < (int)k; ++i)
    printf("%d%c", res2[i] + 1, i == k - 1 ? '\n' : ' ');
  return 0;
}

```