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 MAXN = 1000;
const int MAXM = MAXN * MAXN * 2;
int n, k;
int cnt[MAXN + 10];
struct et {
  int t;
  et* n;
  et() {}
  et(int _t, et* _n) : t(_t), n(_n) {}
} * e[MAXN + 10], store[MAXM + 10], *loc;
bool fun(int id, int left) {
  if (id > n) return true;
  if (left < 0) return false;
  if (cnt[id]) return fun(id + 1, left);
  int cnter = 0;
  for (et* i = e[id]; i; i = i->n) cnter += !cnt[i->t];
  for (et* i = e[id]; i; i = i->n) cnt[i->t]++;
  if (fun(id + 1, left - cnter)) return true;
  for (et* i = e[id]; i; i = i->n) cnt[i->t]--;
  cnt[id]++;
  if (cnter > 1 && fun(id + 1, left - 1)) return true;
  cnt[id]--;
  return false;
}
inline long long sqr(int x) { return x * (long long)x; }
int x[MAXN + 10], y[MAXN + 10];
long long storeD[MAXN + 10][MAXN + 10];
bool can(long long ddd) {
  memset(cnt, 0, sizeof(cnt));
  memset(e, 0, sizeof(e));
  loc = store;
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++)
      if (storeD[i][j] > ddd) e[i] = new (loc++) et(j, e[i]);
  return fun(1, k);
}
int main() {
  scanf("%d%d", &n, &k);
  for (int i = 1; i <= n; i++) {
    scanf("%d%d", &x[i], &y[i]);
  }
  vector<long long> ds;
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= i; j++)
      ds.push_back(storeD[i][j] = storeD[j][i] =
                       sqr(x[i] - x[j]) + sqr(y[i] - y[j]));
  sort(ds.begin(), ds.end());
  ds.erase(unique(ds.begin(), ds.end()), ds.end());
  int l = 0, r = ds.size() - 1, mid = (l + r) >> 1;
  while (l < r) {
    if (can(ds[mid]))
      r = mid;
    else
      l = mid + 1;
    mid = (l + r) >> 1;
  }
  can(ds[mid]);
  for (int i = 1; i <= n; i++)
    if (cnt[i]) k--, printf("%d ", i);
  for (int i = 1; k && i <= n; i++)
    if (!cnt[i]) k--, printf("%d ", i);
  return 0;
}