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 oo = 1047483647, maxn = 1100;
int n, i, j, k, dis[maxn][maxn], l, t[maxn], an[maxn], u, tt, s[maxn * maxn],
    tot, du[maxn], mid;
pair<int, int> a[maxn];
bool sol;
struct edge {
  int v;
  edge *next;
} e[maxn * maxn * 2], *g[maxn];
int get(int i, int j) {
  return ((a[i].first - a[j].first) * (a[i].first - a[j].first)) +
         ((a[i].second - a[j].second) * (a[i].second - a[j].second));
}
void add(int i, int j) {
  e[++tt].next = g[i];
  e[tt].v = j;
  g[i] = e + tt;
}
void clean(int tmp) {
  if (++t[tmp] != 1) return;
  an[++u] = tmp;
  edge *p = g[tmp];
  for (; p != NULL; p = p->next)
    if (!t[p->v]) --du[p->v], --du[tmp];
}
void former(int tmp) {
  if (--t[tmp] != 0) return;
  u--;
  edge *p = g[tmp];
  for (; p != NULL; p = p->next)
    if (!t[p->v]) du[p->v]++, du[tmp]++;
}
void dfs(int first, int res) {
  if (first > n) {
    sol = true;
    return;
  }
  if (du[first] == 0 || t[first]) return dfs(first + 1, res);
  if (du[first] > 1 && res) {
    clean(first);
    dfs(first + 1, res - 1);
    if (sol) return;
    former(first);
  }
  if (du[first] <= res) {
    edge *p = g[first];
    res -= du[first];
    for (; p != NULL; p = p->next) clean(p->v);
    dfs(first + 1, res);
    if (sol) return;
    for (p = g[first]; p != NULL; p = p->next) former(p->v);
  }
  return;
}
bool check(int mid) {
  memset(du, 0, sizeof du);
  tt = 0;
  memset(g, 0, sizeof g);
  memset(t, 0, sizeof t);
  u = 0;
  sol = 0;
  for (i = 1; i <= n; i++) {
    for (j = i + 1; j <= n; j++)
      if (dis[i][j] > mid) {
        add(i, j);
        add(j, i);
        du[i]++;
        du[j]++;
      }
  }
  dfs(1, k);
  return sol;
}
int main() {
  scanf("%d%d", &n, &k);
  for (i = 1; i <= n; i++) scanf("%d%d", &a[i].first, &a[i].second);
  if (n == k) {
    for (i = 1; i <= n; i++) printf("%d ", i);
    return 0;
  }
  for (i = 1; i <= n; i++)
    for (j = i + 1; j <= n; j++) dis[i][j] = get(i, j), s[++tot] = dis[i][j];
  sort(s + 1, s + tot + 1);
  tot = unique(s + 1, s + tot + 1) - (s + 1);
  int l = 1, r = tot;
  while (l < r) {
    mid = (l + r) / 2;
    if (check(s[mid]))
      r = mid;
    else
      l = mid + 1;
  }
  check(s[l]);
  for (i = 1; i <= u; i++) printf("%d ", an[i]);
  for (i = 1; u < k; i++)
    if (!t[i]) printf("%d ", i), u++;
  return 0;
}