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 t, k, n, ds[1005][1005], ans = -1, dis;
bool del[1005];
vector<int> vec[1005], val;
struct box {
  int x, y;
} p[1005];
bool dfs(int x) {
  vector<int> recover;
  bool re = false;
  int degree = 0;
  vector<int>::iterator iter;
  if (t > k) return false;
  if (x == n + 1) {
    if (ans == dis) {
      for (int i = 1; i <= n; i++)
        if (del[i]) printf("%d ", i);
      for (int i = 1; i <= n && k > t; i++)
        if (!del[i]) printf("%d ", i), k--;
    }
    return true;
  }
  if (del[x]) return dfs(x + 1);
  for (iter = vec[x].begin(); iter != vec[x].end(); iter++) {
    if (!del[*iter]) {
      recover.push_back(*iter);
      t++;
    }
    del[*iter] = true;
  }
  if (dfs(x + 1)) re = true;
  for (iter = recover.begin(); iter != recover.end(); iter++) {
    del[*iter] = false, t--;
    degree++;
  }
  if (re) return true;
  if (degree > 1) {
    del[x] = true;
    t++;
    if (dfs(x + 1)) re = true;
    del[x] = false;
    t--;
  }
  return re;
}
bool check() {
  memset(del, false, sizeof(del));
  int i, j;
  t = 0;
  for (i = 1; i <= n; i++) vec[i].clear();
  for (i = 1; i <= n; i++)
    for (j = i + 1; j <= n; j++)
      if (ds[i][j] > dis) {
        vec[i].push_back(j);
        vec[j].push_back(i);
      }
  for (i = 1; i <= n; i++)
    if (vec[i].size() > k) {
      del[i] = true;
      t++;
    }
  return dfs(1);
}
int main() {
  scanf("%d%d", &n, &k);
  int i, j, left, right, mid;
  for (i = 1; i <= n; i++) scanf("%d%d", &p[i].x, &p[i].y);
  for (i = 1; i <= n; i++)
    for (j = 1; j <= n; j++) {
      ds[i][j] = (p[i].x - p[j].x) * (p[i].x - p[j].x) +
                 (p[i].y - p[j].y) * (p[i].y - p[j].y);
      val.push_back(ds[i][j]);
    }
  sort(val.begin(), val.end());
  vector<int>::iterator it;
  it = unique(val.begin(), val.end());
  right = it - val.begin() - 1;
  left = 0;
  while (right - left > 1) {
    mid = (left + right) >> 1;
    dis = val[mid];
    if (check())
      right = mid;
    else
      left = mid + 1;
  }
  dis = val[left];
  if (check())
    mid = left;
  else
    mid = right;
  ans = dis = val[mid];
  check();
}