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;
pair<int, int> point[1010];
int n, k;
vector<int> diameter;
int sqr(int x) { return x * x; }
int dis(const pair<int, int> &a, const pair<int, int> &b) {
  return sqr(a.first - b.first) + sqr(a.second - b.second);
}
vector<int> E[1010];
int deg[1010], selected[1010];
bool Add(int x) {
  selected[x]++;
  if (selected[x] > 1) return 0;
  for (typeof((E[x]).begin()) y = (E[x]).begin(); y != (E[x]).end(); y++)
    deg[*y]--;
  return 1;
}
bool Del(int x) {
  selected[x]--;
  if (selected[x]) return 0;
  for (typeof((E[x]).begin()) y = (E[x]).begin(); y != (E[x]).end(); y++)
    deg[*y]++;
  return 1;
}
bool dfs(int x, int k) {
  if (k < 0) return 0;
  if (x == n + 1) return 1;
  if (!deg[x] || selected[x]) return dfs(x + 1, k);
  if (deg[x] != 1) {
    Add(x);
    if (dfs(x + 1, k - 1)) return 1;
    Del(x);
  }
  for (typeof((E[x]).begin()) y = (E[x]).begin(); y != (E[x]).end(); y++)
    k -= Add(*y);
  if (dfs(x + 1, k)) return 1;
  for (typeof((E[x]).begin()) y = (E[x]).begin(); y != (E[x]).end(); y++)
    k += Del(*y);
  return 0;
}
bool ok(int diameter) {
  for (int i = (1); i <= (n); i++) E[i].clear(), deg[i] = 0, selected[i] = 0;
  for (int i = (1); i <= (n); i++)
    for (int j = (1); j <= (n); j++)
      if (dis(point[i], point[j]) > diameter) {
        E[i].push_back(j), deg[i]++;
      }
  return dfs(1, k);
}
int main() {
  cin >> n >> k;
  for (int i = (1); i <= (n); i++)
    scanf("%d%d", &point[i].first, &point[i].second);
  for (int i = (1); i <= (n); i++)
    for (int j = (i + 1); j <= (n); j++)
      diameter.push_back(dis(point[i], point[j]));
  sort((diameter).begin(), (diameter).end());
  int L = 0, R = ((int)(diameter).size());
  while (L < R) {
    int M = (L + R) / 2;
    if (ok(diameter[M]))
      R = M;
    else
      L = M + 1;
  }
  ok(diameter[L]);
  for (int i = (1); i <= (n); i++)
    if (selected[i]) cout << i << " ", k--;
  for (int i = (1); i <= (n); i++)
    if (!selected[i] && k) cout << i << " ", k--;
  return 0;
}