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 point {
  int x, y;
};
struct point a[1010];
struct edge {
  int u, v, next, f;
};
struct edge e[2000100];
int n, k, n1, num, flag = 1;
int p[1010], f[1010], b[1010], c[1010], dis[1010][1010];
long long ans = 2100000000;
void add(int u, int v) {
  e[num].u = u;
  e[num].v = v;
  e[num].next = p[u];
  p[u] = num;
  num++;
  e[num].u = v;
  e[num].v = u;
  e[num].next = p[v];
  p[v] = num;
  num++;
}
void dfs(int i, int s) {
  int j, s1, d;
  if (flag || s > k) return;
  if (i == n + 1) {
    flag = 1;
    for (i = 1; i <= n; i++) f[i] = b[i];
    return;
  }
  if (b[i] == 1) {
    dfs(i + 1, s);
    return;
  }
  d = 0;
  j = p[i];
  while (j != -1) {
    if (b[e[j].v] == 0) d++;
    j = e[j].next;
  }
  if (d > 1) {
    b[i] = 1;
    dfs(i + 1, s + 1);
    b[i] = 0;
  }
  s1 = s;
  j = p[i];
  while (j != -1) {
    if (b[e[j].v] == 0) {
      b[e[j].v] = 1;
      s1++;
      e[j].f = 1;
    }
    j = e[j].next;
  }
  dfs(i + 1, s1);
  j = p[i];
  while (j != -1) {
    if (e[j].f) {
      e[j].f = 0;
      b[e[j].v] = 0;
    }
    j = e[j].next;
  }
}
int check(long long x) {
  int i, j;
  num = 0;
  memset(p, -1, sizeof(p));
  for (i = 1; i <= n; i++)
    for (j = i + 1; j <= n; j++)
      if (dis[i][j] > x) {
        add(i, j);
      }
  flag = 0;
  dfs(1, 0);
  return flag;
}
int main() {
  int i, j;
  long long l, r, mid;
  scanf("%d%d", &n, &k);
  for (i = 1; i <= n; i++) scanf("%d%d", &a[i].x, &a[i].y);
  for (i = 1; i <= n; i++)
    for (j = 1; j <= n; j++)
      dis[i][j] = (a[i].x - a[j].x) * (a[i].x - a[j].x) +
                  (a[i].y - a[j].y) * (a[i].y - a[j].y);
  l = 0;
  r = 2100000000;
  while (l <= r) {
    mid = (l + r) / 2;
    if (check(mid)) {
      if (mid < ans) {
        for (i = 1; i <= n; i++) c[i] = f[i];
      }
      r = mid - 1;
    } else
      l = mid + 1;
  }
  n1 = 0;
  for (i = 1; i <= n; i++) n1 += c[i];
  flag = 0;
  for (i = 1; i <= n; i++)
    if (c[i] == 1 || n1 < k) {
      if (flag)
        printf(" ");
      else
        flag = 1;
      printf("%d", i);
      if (c[i] == 0) n1++;
    }
  return 0;
}