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 INF = 0x3f3f3f3f;
const long double EPS = 1e-6;
const int N = 1010;
long long qread() {
  char c = getchar();
  int neg = 1;
  long long val = 0;
  while (c != '-' && !isdigit(c)) c = getchar();
  if (c == '-') c = getchar(), neg = -1;
  while (isdigit(c)) val = (val << 3) + (val << 1) + c - '0', c = getchar();
  return neg * val;
}
struct Point {
  int x, y;
  Point(int x = 0, int y = 0) : x(x), y(y) {}
};
double dist(Point a, Point b) {
  return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}
int n, k;
vector<Point> a;
int deg[N];
vector<int> G[N];
bool deleted[N], ans[N];
void remove(int x) {
  deleted[x] = true;
  for (auto v : G[x]) {
    deg[v]--;
    deg[x]--;
  }
}
void recover(int x) {
  deleted[x] = false;
  for (auto v : G[x]) {
    deg[v]++;
    deg[x]++;
  }
}
bool solve(int k) {
  int leaf = -1, x = -1;
  for (int(i) = 0; (i) < (int)n; (i)++)
    if (!deleted[i] && deg[i] == 1) {
      leaf = i;
      break;
    }
  if (leaf != -1) {
    auto it = G[leaf].begin();
    for (; it != G[leaf].end(); it++) {
      if (!deleted[*it]) break;
    }
    int v = *it;
    remove(v);
    if (k > 0 && solve(k - 1)) return true;
    recover(v);
    return false;
  }
  int maxdeg = 0;
  for (int(i) = 0; (i) < (int)n; (i)++)
    if (!deleted[i] && deg[i] > maxdeg) {
      maxdeg = deg[i];
      x = i;
    }
  if (maxdeg == 0) return true;
  if (k == 0) return false;
  remove(x);
  if (solve(k - 1)) return true;
  recover(x);
  if (maxdeg > 1 && maxdeg <= k) {
    vector<int> ne;
    for (auto v : G[x])
      if (!deleted[v]) ne.push_back(v);
    for (auto i : ne) remove(i);
    if (solve(k - maxdeg)) return true;
    for (auto i : ne) recover(i);
  }
  return false;
}
bool check(int x) {
  for (int(i) = 0; (i) < (int)n; (i)++) G[i].clear();
  memset(deg, 0, sizeof(deg));
  for (int(i) = 0; (i) < (int)n; (i)++)
    for (int(j) = 0; (j) < (int)n; (j)++)
      if (dist(a[i], a[j]) > x) {
        G[i].push_back(j);
        deg[i]++;
      }
  memset(deleted, 0, sizeof(deleted));
  return solve(k);
}
int main() {
  n = qread();
  k = qread();
  for (int(i) = 0; (i) < (int)n; (i)++) {
    int x = qread(), y = qread();
    a.push_back(Point(x, y));
  }
  int L = -1, R = 2100000000;
  while (L + 1 < R) {
    int mid = (L + R) >> 1;
    if (check(mid)) {
      for (int(i) = 0; (i) < (int)n; (i)++) ans[i] = deleted[i];
      R = mid;
    } else
      L = mid;
  }
  int rem = k;
  for (int(i) = 0; (i) < (int)n; (i)++)
    if (ans[i]) rem--;
  for (int(i) = 0; (i) < (int)n; (i)++)
    if (rem > 0 && !ans[i]) {
      ans[i] = true;
      rem--;
    }
  for (int(i) = 0; (i) < (int)n; (i)++)
    if (ans[i]) cout << i + 1 << ' ';
  cout << endl;
  return 0;
}