#include <bits/stdc++.h>
using namespace std;
const int N = 1005;
int n, k;
bool e[N][N];
int deg[N];
bool removed[N];
vector<int> atDegree[4];
vector<int> neighbors[N];
void remove(int x) {
  assert(!removed[x]);
  deg[x] = (int)-1e9;
  removed[x] = true;
  for (__typeof(neighbors[x].begin()) it = (neighbors[x].begin());
       it != (neighbors[x]).end(); ++it) {
    if (!removed[*it]) {
      --deg[*it];
      if (deg[*it] == 2) {
        atDegree[2].push_back(*it);
      } else if (deg[*it] == 1) {
        atDegree[1].push_back(*it);
      }
    }
  }
}
void unremove(int x) {
  assert(removed[x]);
  deg[x] = 0;
  removed[x] = false;
  for (__typeof(neighbors[x].begin()) it = (neighbors[x].begin());
       it != (neighbors[x]).end(); ++it) {
    if (!removed[*it]) {
      ++deg[x];
      ++deg[*it];
      if (deg[*it] == 3) {
        atDegree[3].push_back(*it);
      } else if (deg[*it] == 2) {
        atDegree[2].push_back(*it);
      } else if (deg[*it] == 1) {
        atDegree[1].push_back(*it);
      }
    }
  }
  if (deg[x] >= 3) {
    atDegree[3].push_back(x);
  } else if (deg[x] == 2) {
    atDegree[2].push_back(x);
  } else if (deg[x] == 1) {
    atDegree[1].push_back(x);
  }
}
bool go(int rem) {
  if (rem < 0) {
    return false;
  }
  while (!atDegree[1].empty() && deg[atDegree[1].back()] != 1) {
    atDegree[1].pop_back();
  }
  while (!atDegree[2].empty() && deg[atDegree[2].back()] != 2) {
    atDegree[2].pop_back();
  }
  while (!atDegree[3].empty() && deg[atDegree[3].back()] < 3) {
    atDegree[3].pop_back();
  }
  if (!atDegree[1].empty()) {
    int u = atDegree[1].back();
    int v = -1;
    for (__typeof(neighbors[u].begin()) it = (neighbors[u].begin());
         it != (neighbors[u]).end(); ++it) {
      if (!removed[*it]) {
        assert(v == -1);
        v = *it;
      }
    }
    assert(v != -1);
    if (rem >= 1) {
      remove(v);
      if (go(rem - 1)) {
        return true;
      }
      unremove(v);
    }
  } else if (!atDegree[3].empty()) {
    int u = atDegree[3].back();
    vector<int> v;
    for (__typeof(neighbors[u].begin()) it = (neighbors[u].begin());
         it != (neighbors[u]).end(); ++it) {
      if (!removed[*it]) {
        v.push_back(*it);
      }
    }
    assert((int)v.size() >= 3);
    if (rem >= 1) {
      remove(u);
      if (go(rem - 1)) {
        return true;
      }
      unremove(u);
    }
    if ((int)v.size() > rem) {
      return false;
    }
    for (__typeof(v.begin()) it = (v.begin()); it != (v).end(); ++it) {
      remove(*it);
    }
    if (go(rem - (int)v.size())) {
      return true;
    }
    for (__typeof(v.begin()) it = (v.begin()); it != (v).end(); ++it) {
      unremove(*it);
    }
  } else if (!atDegree[2].empty()) {
    int u = atDegree[2].back();
    int v = -1, w = -1;
    for (__typeof(neighbors[u].begin()) it = (neighbors[u].begin());
         it != (neighbors[u]).end(); ++it) {
      if (!removed[*it]) {
        if (v != -1) {
          assert(w == -1);
          w = *it;
        } else {
          v = *it;
        }
      }
    }
    assert(w != -1);
    vector<int> oth;
    for (__typeof(neighbors[v].begin()) it = (neighbors[v].begin());
         it != (neighbors[v]).end(); ++it) {
      if (!removed[*it]) {
        oth.push_back(*it);
      }
    }
    for (__typeof(neighbors[w].begin()) it = (neighbors[w].begin());
         it != (neighbors[w]).end(); ++it) {
      if (!removed[*it]) {
        oth.push_back(*it);
      }
    }
    sort(oth.begin(), oth.end());
    oth.erase(unique(oth.begin(), oth.end()), oth.end());
    if ((int)oth.size() <= rem) {
      for (__typeof(oth.begin()) it = (oth.begin()); it != (oth).end(); ++it) {
        remove(*it);
      }
      if (go(rem - (int)oth.size())) {
        return true;
      }
      for (__typeof(oth.begin()) it = (oth.begin()); it != (oth).end(); ++it) {
        unremove(*it);
      }
    }
    if (rem >= 2) {
      remove(v);
      remove(w);
      if (go(rem - 2)) {
        return true;
      }
      unremove(v);
      unremove(w);
    }
  } else {
    return true;
  }
  return false;
}
bool solve() {
  memset(removed, 0, sizeof(removed));
  int rem = k;
  for (int i = 1; i <= n; ++i) {
    int cdeg = 0;
    for (int j = 1; j <= n; ++j) {
      cdeg += e[i][j];
    }
    if (cdeg > k) {
      --rem;
      removed[i] = true;
    }
  }
  if (rem < 0) {
    return false;
  }
  for (int i = 1; i <= n; ++i) {
    neighbors[i].clear();
  }
  int nEdges = 0;
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= n; ++j) {
      if (!removed[i] && !removed[j] && e[i][j]) {
        neighbors[i].push_back(j);
        ++nEdges;
      }
    }
    deg[i] = neighbors[i].size();
  }
  if (nEdges > 2 * k * k) {
    return false;
  }
  for (int i = 1; i <= 3; ++i) {
    atDegree[i].clear();
  }
  for (int i = 1; i <= n; ++i) {
    if (!removed[i]) {
      if (deg[i] >= 3) {
        atDegree[3].push_back(i);
      } else if (deg[i] >= 1) {
        atDegree[deg[i]].push_back(i);
      }
    }
  }
  return go(rem);
}
long long dist[N][N];
void prep(long long c) {
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= n; ++j) {
      e[i][j] = (dist[i][j] > c);
    }
  }
}
pair<int, int> points[N];
long long sq(int x) { return x * (long long)x; }
int main() {
  scanf("%d %d", &n, &k);
  for (int i = 1; i <= n; ++i) {
    scanf("%d %d", &points[i].first, &points[i].second);
  }
  long long md = 0;
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= n; ++j) {
      dist[i][j] = sq(points[i].first - points[j].first) +
                   sq(points[i].second - points[j].second);
      md = max(md, dist[i][j]);
    }
  }
  long long l = 0, r = md;
  while (l < r) {
    long long c = (l + r) / 2;
    prep(c);
    if (solve()) {
      r = c;
    } else {
      l = c + 1;
    }
  }
  prep(l);
  solve();
  int nRemoved = 0;
  for (int i = 1; i <= n; ++i) {
    nRemoved += removed[i];
  }
  for (int i = 1; i <= n; ++i) {
    if (!removed[i] && nRemoved < k) {
      ++nRemoved;
      removed[i] = true;
    }
  }
  for (int i = 1; i <= n; ++i) {
    if (removed[i]) {
      printf("%d", i);
      if (--nRemoved > 0) {
        printf(" ");
      }
    }
  }
  printf("\n");
}

### Prompt

Construct a CPP code solution to the problem outlined:

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;
const int N = 1005;
int n, k;
bool e[N][N];
int deg[N];
bool removed[N];
vector<int> atDegree[4];
vector<int> neighbors[N];
void remove(int x) {
  assert(!removed[x]);
  deg[x] = (int)-1e9;
  removed[x] = true;
  for (__typeof(neighbors[x].begin()) it = (neighbors[x].begin());
       it != (neighbors[x]).end(); ++it) {
    if (!removed[*it]) {
      --deg[*it];
      if (deg[*it] == 2) {
        atDegree[2].push_back(*it);
      } else if (deg[*it] == 1) {
        atDegree[1].push_back(*it);
      }
    }
  }
}
void unremove(int x) {
  assert(removed[x]);
  deg[x] = 0;
  removed[x] = false;
  for (__typeof(neighbors[x].begin()) it = (neighbors[x].begin());
       it != (neighbors[x]).end(); ++it) {
    if (!removed[*it]) {
      ++deg[x];
      ++deg[*it];
      if (deg[*it] == 3) {
        atDegree[3].push_back(*it);
      } else if (deg[*it] == 2) {
        atDegree[2].push_back(*it);
      } else if (deg[*it] == 1) {
        atDegree[1].push_back(*it);
      }
    }
  }
  if (deg[x] >= 3) {
    atDegree[3].push_back(x);
  } else if (deg[x] == 2) {
    atDegree[2].push_back(x);
  } else if (deg[x] == 1) {
    atDegree[1].push_back(x);
  }
}
bool go(int rem) {
  if (rem < 0) {
    return false;
  }
  while (!atDegree[1].empty() && deg[atDegree[1].back()] != 1) {
    atDegree[1].pop_back();
  }
  while (!atDegree[2].empty() && deg[atDegree[2].back()] != 2) {
    atDegree[2].pop_back();
  }
  while (!atDegree[3].empty() && deg[atDegree[3].back()] < 3) {
    atDegree[3].pop_back();
  }
  if (!atDegree[1].empty()) {
    int u = atDegree[1].back();
    int v = -1;
    for (__typeof(neighbors[u].begin()) it = (neighbors[u].begin());
         it != (neighbors[u]).end(); ++it) {
      if (!removed[*it]) {
        assert(v == -1);
        v = *it;
      }
    }
    assert(v != -1);
    if (rem >= 1) {
      remove(v);
      if (go(rem - 1)) {
        return true;
      }
      unremove(v);
    }
  } else if (!atDegree[3].empty()) {
    int u = atDegree[3].back();
    vector<int> v;
    for (__typeof(neighbors[u].begin()) it = (neighbors[u].begin());
         it != (neighbors[u]).end(); ++it) {
      if (!removed[*it]) {
        v.push_back(*it);
      }
    }
    assert((int)v.size() >= 3);
    if (rem >= 1) {
      remove(u);
      if (go(rem - 1)) {
        return true;
      }
      unremove(u);
    }
    if ((int)v.size() > rem) {
      return false;
    }
    for (__typeof(v.begin()) it = (v.begin()); it != (v).end(); ++it) {
      remove(*it);
    }
    if (go(rem - (int)v.size())) {
      return true;
    }
    for (__typeof(v.begin()) it = (v.begin()); it != (v).end(); ++it) {
      unremove(*it);
    }
  } else if (!atDegree[2].empty()) {
    int u = atDegree[2].back();
    int v = -1, w = -1;
    for (__typeof(neighbors[u].begin()) it = (neighbors[u].begin());
         it != (neighbors[u]).end(); ++it) {
      if (!removed[*it]) {
        if (v != -1) {
          assert(w == -1);
          w = *it;
        } else {
          v = *it;
        }
      }
    }
    assert(w != -1);
    vector<int> oth;
    for (__typeof(neighbors[v].begin()) it = (neighbors[v].begin());
         it != (neighbors[v]).end(); ++it) {
      if (!removed[*it]) {
        oth.push_back(*it);
      }
    }
    for (__typeof(neighbors[w].begin()) it = (neighbors[w].begin());
         it != (neighbors[w]).end(); ++it) {
      if (!removed[*it]) {
        oth.push_back(*it);
      }
    }
    sort(oth.begin(), oth.end());
    oth.erase(unique(oth.begin(), oth.end()), oth.end());
    if ((int)oth.size() <= rem) {
      for (__typeof(oth.begin()) it = (oth.begin()); it != (oth).end(); ++it) {
        remove(*it);
      }
      if (go(rem - (int)oth.size())) {
        return true;
      }
      for (__typeof(oth.begin()) it = (oth.begin()); it != (oth).end(); ++it) {
        unremove(*it);
      }
    }
    if (rem >= 2) {
      remove(v);
      remove(w);
      if (go(rem - 2)) {
        return true;
      }
      unremove(v);
      unremove(w);
    }
  } else {
    return true;
  }
  return false;
}
bool solve() {
  memset(removed, 0, sizeof(removed));
  int rem = k;
  for (int i = 1; i <= n; ++i) {
    int cdeg = 0;
    for (int j = 1; j <= n; ++j) {
      cdeg += e[i][j];
    }
    if (cdeg > k) {
      --rem;
      removed[i] = true;
    }
  }
  if (rem < 0) {
    return false;
  }
  for (int i = 1; i <= n; ++i) {
    neighbors[i].clear();
  }
  int nEdges = 0;
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= n; ++j) {
      if (!removed[i] && !removed[j] && e[i][j]) {
        neighbors[i].push_back(j);
        ++nEdges;
      }
    }
    deg[i] = neighbors[i].size();
  }
  if (nEdges > 2 * k * k) {
    return false;
  }
  for (int i = 1; i <= 3; ++i) {
    atDegree[i].clear();
  }
  for (int i = 1; i <= n; ++i) {
    if (!removed[i]) {
      if (deg[i] >= 3) {
        atDegree[3].push_back(i);
      } else if (deg[i] >= 1) {
        atDegree[deg[i]].push_back(i);
      }
    }
  }
  return go(rem);
}
long long dist[N][N];
void prep(long long c) {
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= n; ++j) {
      e[i][j] = (dist[i][j] > c);
    }
  }
}
pair<int, int> points[N];
long long sq(int x) { return x * (long long)x; }
int main() {
  scanf("%d %d", &n, &k);
  for (int i = 1; i <= n; ++i) {
    scanf("%d %d", &points[i].first, &points[i].second);
  }
  long long md = 0;
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= n; ++j) {
      dist[i][j] = sq(points[i].first - points[j].first) +
                   sq(points[i].second - points[j].second);
      md = max(md, dist[i][j]);
    }
  }
  long long l = 0, r = md;
  while (l < r) {
    long long c = (l + r) / 2;
    prep(c);
    if (solve()) {
      r = c;
    } else {
      l = c + 1;
    }
  }
  prep(l);
  solve();
  int nRemoved = 0;
  for (int i = 1; i <= n; ++i) {
    nRemoved += removed[i];
  }
  for (int i = 1; i <= n; ++i) {
    if (!removed[i] && nRemoved < k) {
      ++nRemoved;
      removed[i] = true;
    }
  }
  for (int i = 1; i <= n; ++i) {
    if (removed[i]) {
      printf("%d", i);
      if (--nRemoved > 0) {
        printf(" ");
      }
    }
  }
  printf("\n");
}

```