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 = 1200;
struct point {
  int x, y;
} p[MaxN];
int dd[MaxN][MaxN], ans[MaxN * MaxN];
inline int dist(point a, point b) {
  return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}
int precalc(int n) {
  int len = 0;
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++) ans[len++] = dd[i][j] = dist(p[i], p[j]);
  sort(ans, ans + len);
  return unique(ans, ans + len) - ans;
}
struct edge {
  int vj;
  edge *next;
} * g[MaxN], da[MaxN * MaxN];
int used[MaxN];
int num[MaxN], der[MaxN];
int tot = 0, V = 0;
void add(int u, int v) {
  da[tot].vj = v;
  da[tot].next = g[u];
  g[u] = da + tot++;
  der[u]++;
}
int getnum(int x) {
  if (num[x] > 0)
    return num[x];
  else
    return num[x] = ++V;
}
void remove(int x, int tt) {
  used[x] = tt;
  for (edge *p = g[x]; p != NULL; p = p->next) der[p->vj]--;
}
void remuse(int x, int tt) {
  used[x] = 0;
  for (edge *p = g[x]; p != NULL; p = p->next) der[p->vj]++;
}
bool succ;
void dfs(int rest, int dep) {
  int k = -1;
  if (rest < 0) return;
  for (int i = 1; i <= V; i++)
    if (!used[i]) {
      if (k == -1 || der[k] < der[i]) k = i;
    }
  if (!der[k]) {
    succ = true;
    return;
  }
  remove(k, dep);
  dfs(rest - 1, dep + 1);
  if (succ) return;
  remuse(k, dep);
  if (der[k] > 1 && der[k] <= rest) {
    int tmp = der[k];
    for (edge *p = g[k]; p != NULL; p = p->next)
      if (used[p->vj] == 0) remove(p->vj, dep);
    dfs(rest - tmp, dep + 1);
    if (succ) return;
    for (edge *p = g[k]; p != NULL; p = p->next)
      if (used[p->vj] == dep) remuse(p->vj, dep);
  }
}
bool ex[MaxN];
bool check(int x, int n, int k) {
  int tt = 0;
  vector<int> vt;
  memset(num, 0, sizeof num);
  memset(der, 0, sizeof der);
  memset(g, 0, sizeof g);
  memset(ex, 0, sizeof ex);
  memset(used, 0, sizeof used);
  tot = V = 0;
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
      if (dd[i][j] > x) {
        if (!ex[i] && !ex[j]) {
          tt++;
          ex[i] = ex[j] = true;
          vt.push_back(i);
          vt.push_back(j);
        }
        add(getnum(i), getnum(j));
      }
  if (vt.size() <= k) {
    for (int i = 0; i < vt.size(); i++) used[num[vt[i]]] = 1;
    return true;
  }
  succ = false;
  if (tt <= k) dfs(k, 1);
  return succ;
}
int main() {
  int n, k;
  cin >> n >> k;
  for (int i = 0; i < n; i++) cin >> p[i].x >> p[i].y;
  vector<int> res;
  int low = 0, high = precalc(n) - 1;
  while (low < high) {
    int mid = (low + high) >> 1;
    if (check(ans[mid], n, k))
      high = mid;
    else
      low = mid + 1;
  }
  check(ans[low], n, k);
  for (int i = 0; i < n; i++)
    if (used[num[i]]) res.push_back(i + 1);
  for (int i = 0; i < n && res.size() < k; i++)
    if (!used[num[i]]) res.push_back(i + 1);
  for (int i = 0; i < res.size(); i++) cout << res[i] << ' ';
  cout << endl;
  return 0;
}