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 N = int(1e6);
const int mod = int(1e9) + 7;
int n, x[2000], y[2000], k, pn;
pair<long long, pair<int, int> > p[N];
bool a[2020];
vector<int> g[2000], ans;
int cnt;
int b[1200][30];
bool ok;
long long sqr(int x) { return 1ll * x * x; }
long long dis(int i, int j) {
  return 1ll * sqr(x[i] - x[j]) + 1ll * sqr(y[i] - y[j]);
}
void init() {
  for (int i = 1; i <= n; i++) {
    a[i] = 0;
    g[i].clear();
  }
}
inline void rec(int v, int cur) {
  if (cur > k || cnt <= k) return;
  if (v == n + 1) {
    cnt = cur;
    if (ok) {
      for (int i = 1; i <= n; i++) {
        if (a[i]) ans.push_back(i);
      }
      for (int i = 1; i <= n; i++) {
        if (!a[i] && ans.size() < k) ans.push_back(i);
      }
      for (int i = 0; i < ans.size(); i++) {
        cout << ans[i] << " ";
      }
      exit(0);
    }
    return;
  }
  if (a[v] || g[v].size() == 0) {
    rec(v + 1, cur);
    return;
  }
  if (g[v].size() == 1) {
    if (a[g[v][0]])
      rec(v + 1, cur);
    else {
      a[g[v][0]] = 1;
      rec(v + 1, cur + 1);
      a[g[v][0]] = 0;
    }
    return;
  }
  if (g[v].size() > k) {
    a[v] = 1;
    rec(v + 1, cur + 1);
    a[v] = 0;
    return;
  }
  int res = 0;
  for (int i = 0; i < g[v].size(); i++) {
    if (!a[g[v][i]]) res++;
    b[v][i] = a[g[v][i]];
    a[g[v][i]] = 1;
  }
  rec(v + 1, cur + res);
  for (int i = 0; i < g[v].size(); i++) {
    a[g[v][i]] = b[v][i];
  }
  if (res > 1) {
    a[v] = 1;
    rec(v + 1, cur + 1);
    a[v] = 0;
  }
}
bool check(int m) {
  init();
  for (int i = m; i <= pn; i++) {
    g[p[i].second.first].push_back(p[i].second.second);
    g[p[i].second.second].push_back(p[i].second.first);
  }
  cnt = mod;
  rec(1, 0);
  return (cnt <= k);
}
int main() {
  scanf("%d%d", &n, &k);
  for (int i = 1; i <= n; i++) {
    scanf("%d%d", &x[i], &y[i]);
  }
  for (int i = 1; i <= n; i++) {
    for (int j = i + 1; j <= n; j++) {
      p[++pn] = make_pair(dis(i, j), make_pair(i, j));
    }
  }
  sort(p + 1, p + pn + 1);
  int l = 0, r = pn, mid;
  while (r - l > 1) {
    mid = (r + l) / 2;
    if (check(mid)) {
      r = mid;
    } else
      l = mid;
  }
  ok = 1;
  check(r);
  return 0;
}