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 dcmp(double x) {
  if (fabs(x) < 1e-9) return 0;
  return x < 1e-9 ? -1 : 1;
}
struct road {
  int x, next;
} r[1005 * 1005 * 2];
int N, K, num;
int st[1005], w;
int in[1005], ans[1005];
int tv[1005][1005];
int vis[1005], tot;
int rk[1005];
double x[1005], y[1005];
double dis[1005][1005], len[1005 * 1005];
void add(int x, int y) {
  r[++w].x = y;
  r[w].next = st[x];
  st[x] = w;
}
double dist(int a, int b) {
  return sqrt((x[a] - x[b]) * (x[a] - x[b]) + (y[a] - y[b]) * (y[a] - y[b]));
}
inline void ad(int fr, int x) {
  int i;
  tv[fr][x] = vis[x], tot += (!tv[fr][x]), vis[x] = 1;
  if (!tv[fr][x])
    for (i = st[x]; i; i = r[i].next)
      if (!vis[r[i].x]) in[r[i].x]--;
  in[x] = 0;
}
inline void del(int fr, int x) {
  int i;
  vis[x] = tv[fr][x], tot -= (!tv[fr][x]);
  if (!tv[fr][x])
    for (i = st[x]; i; i = r[i].next)
      if (!vis[r[i].x]) in[r[i].x]++, in[x]++;
}
bool Dfs(int x) {
  int i, j, tmp = 0, get = 0;
  int y = x;
  x = rk[x];
  if (y > N) {
    for (i = 1; i <= N; i++) ans[i] = vis[i];
    return true;
  }
  if (!in[x]) return Dfs(y + 1);
  if (in[x] != 1 && tot + (!vis[x]) <= K) {
    ad(x, x), get = Dfs(y + 1), del(x, x);
  }
  if (get) return true;
  for (i = st[x]; i; i = r[i].next) tmp += (!vis[r[i].x]);
  if ((!vis[x]) && tot + tmp <= K) {
    for (i = st[x]; i; i = r[i].next) ad(x, r[i].x);
    get = Dfs(y + 1);
    for (i = st[x]; i; i = r[i].next) del(x, r[i].x);
  }
  if (get) return true;
  return false;
}
bool Work(int mid) {
  int i, j;
  memset(st, 0, sizeof(st)), w = 0;
  memset(in, 0, sizeof(in));
  for (i = 1; i <= N; i++)
    for (j = i + 1; j <= N; j++) {
      if (dcmp(dis[i][j] - len[mid]) > 0)
        add(i, j), add(j, i), in[i]++, in[j]++;
    }
  memset(vis, 0, sizeof(vis)), tot = 0;
  return Dfs(1);
}
int main() {
  int i, j, cnt;
  int l, r, mid;
  scanf("%d %d", &N, &K);
  for (i = 1; i <= N; i++) scanf("%lf %lf", &x[i], &y[i]), rk[i] = i;
  random_shuffle(rk + 1, rk + 1 + N);
  for (i = 1; i <= N; i++)
    for (j = i + 1; j <= N; j++) {
      dis[i][j] = dis[j][i] = dist(i, j);
      len[++num] = dis[i][j];
    }
  len[++num] = 0, sort(len + 1, len + 1 + num), len[0] = -1;
  for (i = 1, j = 0; i <= num; i++)
    if (dcmp(len[i] - len[i - 1]) != 0) len[++j] = len[i];
  num = r = j, l = 1;
  while (l <= r) {
    mid = (l + r) / 2;
    if (Work(mid))
      r = mid - 1;
    else
      l = mid + 1;
  }
  Work(l);
  for (i = 1, cnt = 0; i <= N; i++)
    if (ans[i]) printf("%d ", i), cnt++;
  for (i = 1; i <= N, cnt < K; i++)
    if (!ans[i]) printf("%d ", i), cnt++;
  printf("\n");
  return 0;
}