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