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 N = 1005;
int n, k, i, j, en, mid, rn;
bool check;
struct edge {
  int x, y;
  long double z;
  edge() {}
  edge(int X, int Y, long double Z) : x(X), y(Y), z(Z) {}
  inline bool operator<(const edge &RHS) const { return z > RHS.z; }
};
int x[N], y[N];
edge e[N * N];
int deg[N];
bool inAns[N];
bool removed[N];
vector<int> cg[N];
void rec(int handled) {
  if (rn > k) return;
  if (check) return;
  if (handled == mid) {
    check = true;
    for (int i = 1; i <= n; i++) inAns[i] = removed[i];
    return;
  }
  int x = e[handled + 1].x;
  int y = e[handled + 1].y;
  if (removed[x] || removed[y])
    rec(handled + 1);
  else {
    if (deg[x] < deg[y]) swap(x, y);
    if (deg[x] <= k) {
      int nrem[32] = {0};
      for (int i = 0; i < (int)cg[x].size(); i++) {
        if (removed[cg[x][i]]) continue;
        nrem[++nrem[0]] = cg[x][i];
        rn++;
        removed[cg[x][i]] = true;
        if (rn > k) break;
      }
      if (rn <= k) rec(handled + 1);
      while (nrem[0] > 0) {
        removed[nrem[nrem[0]]] = false;
        rn--;
        nrem[0]--;
      }
    }
    if (deg[x] != 1) {
      rn++;
      removed[x] = true;
      rec(handled + 1);
      removed[x] = false;
      rn--;
    }
  }
}
int main() {
  scanf("%d%d", &n, &k);
  for (int i = 1; i <= n; i++) scanf("%d%d", x + i, y + i);
  for (int i = 1; i < n; i++)
    for (int j = i + 1; j <= n; j++)
      e[++en] = edge(i, j, hypot(x[i] - x[j], y[i] - y[j]));
  sort(e + 1, e + en + 1);
  int l = 1, r = en, qq = 0, lm = -1;
  for (int iter = 0; iter < 20; iter++) {
    mid = (l + r) / 2;
    if (mid == lm) break;
    lm = mid;
    memset(deg, 0, sizeof(deg));
    for (int i = 1; i <= n; i++) cg[i].clear();
    for (int i = 1; i <= mid; i++) {
      deg[e[i].x]++;
      deg[e[i].y]++;
      cg[e[i].x].push_back(e[i].y);
      cg[e[i].y].push_back(e[i].x);
    }
    memset(removed, 0, sizeof(removed));
    rn = 0;
    check = false;
    rec(0);
    if (check) {
      qq = max(qq, mid);
      l = mid + 1;
    } else
      r = mid;
  }
  vector<int> ans;
  for (int i = 1; i <= n; i++)
    if (inAns[i]) ans.push_back(i);
  for (int i = 1; i <= n; i++) {
    if (!inAns[i] && ans.size() < k) ans.push_back(i);
  }
  sort(ans.begin(), ans.end());
  for (int i = 0; i < (int)ans.size(); i++) printf("%d ", ans[i]);
  puts("");
  return 0;
}