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 int maxn = 1010;
int x[maxn], y[maxn], l, en, n, k, dist[maxn][maxn], d[maxn * maxn], tag[maxn];
struct edge {
  int e;
  edge *next;
} * v[maxn], ed[maxn * maxn << 1];
void add_edge(int s, int e) {
  en++;
  ed[en].next = v[s];
  v[s] = ed + en;
  v[s]->e = e;
}
bool dfs(int p, int k) {
  if (p == n + 1) return true;
  if (tag[p]) return dfs(p + 1, k);
  for (edge *e = v[p]; e; e = e->next) {
    if (!tag[e->e]) k--;
    tag[e->e]++;
  }
  if (k >= 0 && dfs(p + 1, k)) return true;
  int tmp = k;
  for (edge *e = v[p]; e; e = e->next) {
    tag[e->e]--;
    if (!tag[e->e]) k++;
  }
  k--;
  tag[p]++;
  if (k >= 0 && k > tmp && dfs(p + 1, k)) return true;
  k++;
  tag[p]--;
  return false;
}
bool check(int p) {
  for (int a = 1; a <= n; a++) tag[a] = 0, v[a] = NULL;
  en = 0;
  for (int a = 1; a <= n; a++)
    for (int b = 1; b <= n; b++)
      if (dist[a][b] > d[p]) add_edge(a, b);
  return dfs(1, k);
}
int main() {
  scanf("%d%d", &n, &k);
  for (int a = 1; a <= n; a++) scanf("%d%d", &x[a], &y[a]);
  for (int a = 1; a <= n; a++)
    for (int b = a + 1; b <= n; b++) {
      dist[a][b] = dist[b][a] =
          (x[a] - x[b]) * (x[a] - x[b]) + (y[a] - y[b]) * (y[a] - y[b]);
      l++;
      d[l] = dist[a][b];
    }
  sort(d + 1, d + l + 1);
  l = unique(d + 1, d + l + 1) - d - 1;
  int r = l;
  l = 0;
  while (l + 1 != r) {
    int m = (l + r) >> 1;
    if (check(m))
      r = m;
    else
      l = m;
  }
  check(r);
  for (int a = 1; a <= n; a++)
    if (tag[a]) {
      k--;
      printf("%d", a);
      if (k == 0)
        printf("\n");
      else
        printf(" ");
    }
  for (int a = 1; a <= n && k; a++)
    if (!tag[a]) {
      k--;
      printf("%d", a);
      if (k == 0)
        printf("\n");
      else
        printf(" ");
    }
  return 0;
}