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;
int N;
int x[1010], y[1010], dist[1010][1010];
bool graph[1010][1010];
int deg[1010];
bool used[1010];
bool ans[1010];
void use(int x) {
  int i;
  used[x] = true;
  for ((i) = 0; (i) < (int)(N); (i)++)
    if (graph[x][i]) {
      deg[x]--;
      deg[i]--;
    }
}
void unuse(int x) {
  int i;
  used[x] = false;
  for ((i) = 0; (i) < (int)(N); (i)++)
    if (graph[x][i]) {
      deg[x]++;
      deg[i]++;
    }
}
bool dfs(int K) {
  int x = -1, leaf = -1, maxdeg = 0, i;
  for ((i) = 0; (i) < (int)(N); (i)++)
    if (!used[i] && deg[i] == 1) {
      leaf = i;
      break;
    }
  if (leaf != -1) {
    for ((i) = 0; (i) < (int)(N); (i)++)
      if (!used[i] && graph[leaf][i]) break;
    use(i);
    if (K > 0 && dfs(K - 1)) return true;
    unuse(i);
    return false;
  }
  for ((i) = 0; (i) < (int)(N); (i)++)
    if (!used[i] && deg[i] > maxdeg) {
      maxdeg = deg[i];
      x = i;
    }
  if (maxdeg == 0) return true;
  if (K == 0) return false;
  use(x);
  if (dfs(K - 1)) return true;
  unuse(x);
  if (maxdeg > 1 && maxdeg <= K) {
    vector<int> v;
    for ((i) = 0; (i) < (int)(N); (i)++)
      if (!used[i] && graph[x][i]) v.push_back(i);
    for ((i) = 0; (i) < (int)(v.size()); (i)++) use(v[i]);
    if (dfs(K - maxdeg)) return true;
    for ((i) = 0; (i) < (int)(v.size()); (i)++) unuse(v[i]);
  }
  return false;
}
bool func(int maxdist, int K) {
  int i, j;
  for ((i) = 0; (i) < (int)(N); (i)++)
    for ((j) = 0; (j) < (int)(N); (j)++) graph[i][j] = (dist[i][j] > maxdist);
  for ((i) = 0; (i) < (int)(N); (i)++) deg[i] = 0;
  for ((i) = 0; (i) < (int)(N); (i)++)
    for ((j) = 0; (j) < (int)(N); (j)++)
      if (graph[i][j]) deg[i]++;
  for ((i) = 0; (i) < (int)(N); (i)++) used[i] = false;
  return dfs(K);
}
int main(void) {
  int K, i, j;
  cin >> N >> K;
  for ((i) = 0; (i) < (int)(N); (i)++) cin >> x[i] >> y[i];
  for ((i) = 0; (i) < (int)(N); (i)++)
    for ((j) = 0; (j) < (int)(N); (j)++)
      dist[i][j] =
          (x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]);
  int low = -1, high = 2100000000;
  while (high - low > 1) {
    int mid = (low + high) / 2;
    if (func(mid, K)) {
      for ((i) = 0; (i) < (int)(N); (i)++) ans[i] = used[i];
      high = mid;
    } else {
      low = mid;
    }
  }
  int cnt = K;
  for ((i) = 0; (i) < (int)(N); (i)++)
    if (ans[i]) cnt--;
  for ((i) = 0; (i) < (int)(N); (i)++)
    if (cnt > 0 && !ans[i]) {
      ans[i] = true;
      cnt--;
    }
  bool first = true;
  for ((i) = 0; (i) < (int)(N); (i)++)
    if (ans[i]) {
      if (!first) cout << ' ';
      first = false;
      cout << i + 1;
    }
  cout << endl;
  return 0;
}