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;
int n, m, N, nT, tot;
int g[1111 * 2222], nxt[1111 * 2222], nm, c[1111];
int ch[1111], ans[1111], idx[1111], du[1111], ansn;
pair<int, int> p[1111], b[1111 * 1111];
int q[1111][1111], qtop[1111];
int q2[1111][1111], qt2[1111];
inline int sqr(int x) { return x * x; }
inline int dist(int x, int y) {
  return sqr(p[x].first - p[y].first) + sqr(p[x].second - p[y].second);
}
int cmp(pair<int, int> x, pair<int, int> y) {
  return dist(x.first, x.second) < dist(y.first, y.second);
}
int equ(pair<int, int> x, pair<int, int> y) {
  return dist(x.first, x.second) == dist(y.first, y.second);
}
void addedge(int x, int y) {
  g[nm] = y;
  nxt[nm] = c[x];
  c[x] = nm;
  nm++;
}
void chose_y(int x) {
  if (ch[x] == 1) cout << "CAONIBA" << endl;
  tot--;
  ch[x] = 1;
  for (int k = c[x]; ~k; k = nxt[k]) {
    int j = g[k];
    if (ch[j] != 1) {
      du[j]--, du[x]--;
      q2[x][++qt2[x]] = j;
    }
  }
}
bool chose_n(int x) {
  if (ch[x] == 0) return 1;
  tot++;
  ch[x] = 0;
  for (; qt2[x]; qt2[x]--) {
    du[q2[x][qt2[x]]]++;
    du[x]++;
  }
  return 0;
}
bool dfs(int x) {
  if (tot < 0) return 0;
  if (x > nT) {
    ansn = 0;
    for (int i = 1; i <= n; ++i)
      if (ch[idx[i]] == 1) ans[++ansn] = i;
    return 1;
  }
  if (ch[x] == 1) {
    if (dfs(x + 1)) return 1;
    return 0;
  }
  ch[x] = 0;
  int fk = 0;
  for (int k = c[x]; ~k; k = nxt[k])
    if (g[k] < x && ch[g[k]] != 1) {
      fk = 1;
      break;
    }
  if (fk == 0) {
    for (int k = c[x]; ~k; k = nxt[k]) {
      int j = g[k];
      if (j > x && ch[j] != 1) {
        chose_y(j);
        q[x][++qtop[x]] = j;
      }
    }
    if (dfs(x + 1)) return 1;
    for (; qtop[x] > 0; qtop[x]--) chose_n(q[x][qtop[x]]);
  }
  if (du[x] > 1) {
    chose_y(x);
    if (dfs(x + 1)) return 1;
    chose_n(x);
  }
  return 0;
}
bool cks(int w) {
  memset(ch, 0, sizeof ch);
  int d = dist(b[w].first, b[w].second);
  memset(qtop, 0, sizeof qtop);
  memset(qt2, 0, sizeof qt2);
  tot = m;
  memset(idx, 0, sizeof idx);
  nT = 0;
  memset(c, -1, sizeof c), nm = 0;
  memset(du, 0, sizeof du);
  for (int i = 1; i <= n; ++i)
    for (int j = i + 1; j <= n; ++j)
      if (dist(i, j) > d) {
        int x, y;
        if (!idx[i]) idx[i] = ++nT;
        if (!idx[j]) idx[j] = ++nT;
        x = idx[i], y = idx[j];
        addedge(x, y);
        addedge(y, x);
        du[x]++;
        du[y]++;
      }
  return dfs(1);
}
int main() {
  scanf("%d%d", &n, &m);
  if (m == n - 1) {
    for (int i = 1; i <= m; ++i) printf(i < m ? "%d " : "%d\n", i);
    return 0;
  }
  for (int i = 1; i <= n; ++i) scanf("%d%d", &p[i].first, &p[i].second);
  for (int i = 1; i <= n; ++i)
    for (int j = i + 1; j <= n; ++j) b[++N] = make_pair(i, j);
  b[++N] = make_pair(0, 0);
  sort(b + 1, b + 1 + N, cmp);
  N = unique(b + 1, b + 1 + N, equ) - b - 1;
  int l = 0, r = N + 1;
  while (l + 1 < r) {
    int mid = (l + r) >> 1;
    if (cks(mid))
      r = mid;
    else
      l = mid;
  }
  cks(r);
  memset(du, 0, sizeof du);
  for (int i = 1; i <= ansn; ++i) du[ans[i]] = 1;
  for (int i = 1; i <= n; ++i)
    if (!du[i] && ansn < m) ans[++ansn] = i;
  for (int i = 1; i <= ansn; ++i) printf(i < ansn ? "%d " : "%d\n", ans[i]);
}