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

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
const double PI = acos(-1);
template <class T>
T sqr(T x) {
  return x * x;
}
template <class T>
T alex(T x) {
  return (x > 0) ? x : -x;
}
template <class T>
void read(T& x) {
  x = 0;
  T f = 1;
  char ch = getchar();
  while ((ch < 48 || ch > 57) && ch != 45) ch = getchar();
  if (ch == 45) f = -1, ch = getchar();
  while (ch >= 48 && ch <= 57) x = x * 10 + ch - 48, ch = getchar();
  x *= f;
}
struct Point {
  double x, y;
  Point() {}
  Point(double x, double y) : x(x), y(y) {}
  Point operator+(const Point& p) const { return Point(x + p.x, y + p.y); }
  Point operator-(const Point& p) const { return Point(x - p.x, y - p.y); }
  double operator*(const Point& p) const { return x * x + y * y; }
  void readin() { scanf("%lf%lf", &x, &y); }
} p[1005];
double dis(Point x, Point y) { return sqrt((x - y) * (x - y)); }
int n, k;
vector<int> link_point[1005];
bool del[1005];
int cnt[1005];
vector<pair<int, int> > unlimit;
bool dfs(int ind, int k) {
  if (k < 0) return false;
  if (ind == unlimit.size()) return true;
  if (del[unlimit[ind].first] || del[unlimit[ind].second])
    return dfs(ind + 1, k);
  if (cnt[unlimit[ind].first] != 1 && cnt[unlimit[ind].second] == 1) {
    del[unlimit[ind].first] = true;
    for (int i = (0); i < (link_point[unlimit[ind].first].size()); i++)
      cnt[link_point[unlimit[ind].first][i]]--;
    if (dfs(ind + 1, k - 1)) return true;
    del[unlimit[ind].first] = false;
    for (int i = (0); i < (link_point[unlimit[ind].first].size()); i++)
      cnt[link_point[unlimit[ind].first][i]]++;
  } else if (cnt[unlimit[ind].first] == 1 && cnt[unlimit[ind].second] != 1) {
    del[unlimit[ind].second] = true;
    for (int i = (0); i < (link_point[unlimit[ind].second].size()); i++)
      cnt[link_point[unlimit[ind].second][i]]--;
    if (dfs(ind + 1, k - 1)) return true;
    del[unlimit[ind].second] = false;
    for (int i = (0); i < (link_point[unlimit[ind].second].size()); i++)
      cnt[link_point[unlimit[ind].second][i]]++;
  } else if (cnt[unlimit[ind].first] == 1 && cnt[unlimit[ind].second] == 1) {
    del[unlimit[ind].first] = true;
    for (int i = (0); i < (link_point[unlimit[ind].first].size()); i++)
      cnt[link_point[unlimit[ind].first][i]]--;
    if (dfs(ind + 1, k - 1)) return true;
    del[unlimit[ind].first] = false;
    for (int i = (0); i < (link_point[unlimit[ind].first].size()); i++)
      cnt[link_point[unlimit[ind].first][i]]++;
  } else if (cnt[unlimit[ind].first] != 1 && cnt[unlimit[ind].second] != 1) {
    del[unlimit[ind].first] = true;
    for (int i = (0); i < (link_point[unlimit[ind].first].size()); i++)
      cnt[link_point[unlimit[ind].first][i]]--;
    if (dfs(ind + 1, k - 1)) return true;
    del[unlimit[ind].first] = false;
    for (int i = (0); i < (link_point[unlimit[ind].first].size()); i++)
      cnt[link_point[unlimit[ind].first][i]]++;
    vector<int> del_num;
    del_num.clear();
    for (int i = (0); i < (link_point[unlimit[ind].first].size()); i++)
      if (!del[link_point[unlimit[ind].first][i]]) {
        del_num.push_back(link_point[unlimit[ind].first][i]);
      }
    for (int i = (0); i < (del_num.size()); i++) del[del_num[i]] = true;
    for (int i = (0); i < (del_num.size()); i++) {
      for (int k = (0); k < (link_point[del_num[i]].size()); k++) {
        cnt[link_point[del_num[i]][k]]--;
      }
    }
    if (dfs(ind + 1, k - del_num.size())) return true;
    for (int i = (0); i < (del_num.size()); i++) del[del_num[i]] = false;
    for (int i = (0); i < (del_num.size()); i++) {
      for (int k = (0); k < (link_point[del_num[i]].size()); k++)
        cnt[link_point[del_num[i]][k]]++;
    }
  }
  return false;
}
bool vis[1005];
int cp[1005];
bool dfs(int x) {
  for (int i = (0); i < (link_point[x].size()); i++)
    if (!vis[link_point[x][i]]) {
      vis[link_point[x][i]] = true;
      if (!cp[link_point[x][i]] || dfs(link_point[x][i])) {
        cp[link_point[x][i]] = x;
        return true;
      }
    }
  return false;
}
int ind[1005];
bool cmp(int x, int y) { return cnt[x] > cnt[y]; }
bool check(double mid) {
  for (int i = (1); i <= (n); i++) link_point[i].clear();
  memset(del, 0, sizeof(del));
  unlimit.clear();
  memset(cnt, 0, sizeof(cnt));
  for (int i = (1); i < (n); i++)
    for (int j = (i + 1); j <= (n); j++)
      if (dis(p[i], p[j]) >= mid)
        unlimit.push_back(make_pair(i, j)), cnt[i]++, cnt[j]++,
            link_point[i].push_back(j), link_point[j].push_back(i);
  return dfs(0, k);
}
int ans[1005];
int main() {
  read(n);
  read(k);
  for (int i = (1); i <= (n); i++) p[i].readin();
  double l = 0.0, r = 2e5;
  while (r - l > 1e-3) {
    double m = (l + r) / 2.0;
    if (check(m))
      r = m;
    else
      l = m;
  }
  check(r);
  for (int i = (1); i <= (n); i++)
    if (del[i]) ans[++ans[0]] = i;
  for (int i = (1); i <= (n); i++)
    if (!del[i] && ans[0] < k) ans[++ans[0]] = i;
  for (int i = (1); i <= (k); i++) printf("%d ", ans[i]);
  puts("");
  return 0;
}