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;
struct pt {
  int x, y;
  pt(int _x = 0, int _y = 0) : x(_x), y(_y) {}
  pt operator-(const pt &p2) const { return pt(x - p2.x, y - p2.y); }
  int dist2() const { return x * x + y * y; }
};
const int MAXN = 1000;
int todel[MAXN];
int es[MAXN][MAXN];
int ecnt[MAXN];
int n;
bool go(int pos, int rem) {
  if (pos >= n) {
    for (int i = 0; i < n && rem; i++)
      if (!todel[i]) {
        todel[i] = pos + 1;
        rem--;
      }
    return true;
  }
  if (todel[pos] || !ecnt[pos]) return go(pos + 1, rem);
  int need = 0;
  for (int i = 0; i < ecnt[pos]; i++) {
    int b = es[pos][i];
    if (todel[b]) continue;
    todel[b] = pos + 1;
    need++;
  }
  if (need <= rem && go(pos + 1, rem - need)) return true;
  for (int i = 0; i < ecnt[pos]; i++) {
    int b = es[pos][i];
    if (todel[b] == pos + 1) todel[b] = 0;
  }
  if (rem > 0 && need > 1) {
    todel[pos] = pos + 1;
    if (go(pos + 1, rem - 1)) return true;
    todel[pos] = 0;
  }
  return false;
}
int k;
int ds[MAXN][MAXN];
bool check(int maxd) {
  fprintf(stderr, "check(%d)\n", maxd);
  memset(ecnt, 0, sizeof ecnt);
  for (int a = 0; a < n; a++)
    for (int b = 0; b < n; b++)
      if (ds[a][b] > maxd) {
        es[a][ecnt[a]++] = b;
      }
  memset(todel, 0, sizeof todel);
  return go(0, k);
}
int main() {
  while (scanf("%d%d", &n, &k) >= 1) {
    vector<pt> pts(n);
    for (int i = 0; i < n; i++) scanf("%d%d", &pts[i].x, &pts[i].y);
    if (k + 1 == n) {
      for (int i = 0; i < k; i++) printf("%d%c", i + 1, "\n "[i + 1 < k]);
      continue;
    }
    vector<int> ads;
    for (int a = 0; a < n; a++) {
      ds[a][a] = 0;
      for (int b = a + 1; b < n; b++) {
        ads.push_back(ds[a][b] = ds[b][a] = (pts[b] - pts[a]).dist2());
      }
    }
    sort(ads.begin(), ads.end());
    ads.erase(unique(ads.begin(), ads.end()), ads.end());
    int L = 0, R = ((int)(ads).size()) - 1;
    if (check(ads[L])) R = L;
    assert(check(ads[R]));
    while (L + 1 < R) {
      int M = (L + R) / 2;
      if (check(ads[M]))
        R = M;
      else
        L = M;
    }
    bool res = check(ads[R]);
    assert(res);
    for (int i = 0; i < n; i++)
      if (todel[i]) printf("%d ", i + 1);
    printf("\n");
  }
  return 0;
}