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 INF = 1000000001;
const long double EPS = 1e-9;
const int MOD = 1000000007;
const long long LLINF = 1000000000000000001;
const int maxn = 1042;
const int MAX = 1000;
struct turbostack {
  int prevp[maxn];
  int nextp[maxn];
  bool active[maxn];
  int last;
  int se;
  int size() { return se; }
  void clear() {
    se = 0;
    for (int i = 0; i <= MAX; i++) {
      prevp[i] = 0;
      nextp[i] = 0;
      active[i] = false;
    }
    last = 0;
  }
  bool empty() { return se == 0; }
  int top() { return last; }
  void insert(int a) {
    se++;
    active[a] = true;
    prevp[a] = last;
    nextp[last] = a;
    last = a;
  }
  void erase(int a) {
    if (!active[a]) return;
    active[a] = false;
    se--;
    if (a == last) {
      last = prevp[a];
    }
    if (prevp[nextp[a]] == a) prevp[nextp[a]] = prevp[a];
    if (nextp[prevp[a]] == a) nextp[prevp[a]] = nextp[a];
  }
};
int n, k;
long long x[maxn];
long long y[maxn];
vector<pair<long long, pair<int, int> > > alledges;
vector<long long> distances;
bool ans[maxn];
int deg[maxn];
vector<int> gr[maxn];
turbostack consider;
turbostack oneedge;
long long sq(long long a) { return a * a; }
int kleft;
void remove(int a) {
  ans[a] = true;
  kleft--;
  consider.erase(a);
  oneedge.erase(a);
  for (auto& i : gr[a]) {
    deg[i]--;
    if (!ans[i]) {
      if (deg[i] == 0)
        oneedge.erase(i);
      else if (deg[i] == 1) {
        consider.erase(i);
        oneedge.insert(i);
      }
    }
  }
}
void addback(int a) {
  ans[a] = false;
  kleft++;
  if (deg[a] == 1) oneedge.insert(a);
  if (deg[a] > 1) consider.insert(a);
  for (auto& i : gr[a]) {
    deg[i]++;
    if (!ans[i]) {
      if (deg[i] == 1)
        oneedge.insert(i);
      else if (deg[i] == 2) {
        oneedge.erase(i);
        consider.insert(i);
      }
    }
  }
}
bool fsearch() {
  if (kleft < 0) return false;
  if (!consider.empty()) {
    if (kleft == 0) return false;
    int a = consider.top();
    remove(a);
    if (fsearch()) return true;
    addback(a);
    vector<int> toaddback;
    toaddback.reserve(1001);
    for (auto& i : gr[a])
      if (!ans[i]) {
        toaddback.push_back(i);
        remove(i);
      }
    if (fsearch()) return true;
    for (auto& i : toaddback) addback(i);
    return false;
  } else {
    if (kleft >= ((int)(oneedge).size()) / 2) {
      while (!oneedge.empty()) {
        int a = oneedge.top();
        remove(a);
      }
      return true;
    } else
      return false;
  }
}
bool f(long long dist) {
  for (int i = 1; i <= n; i++) {
    gr[i].clear();
    ans[i] = false;
  }
  consider.clear();
  oneedge.clear();
  kleft = k;
  for (auto& i : alledges)
    if (i.first >= dist) {
      gr[i.second.first].push_back(i.second.second);
      gr[i.second.second].push_back(i.second.first);
    }
  for (int i = 1; i <= n; i++) deg[i] = ((int)(gr[i]).size());
  for (int i = 1; i <= n; i++) {
    if (deg[i] > 1)
      consider.insert(i);
    else if (deg[i] == 1)
      oneedge.insert(i);
  }
  for (int i = 1; i <= n; i++) {
    if (deg[i] > k) remove(i);
  }
  return fsearch();
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cin >> n >> k;
  for (int i = 1; i <= n; i++) cin >> x[i] >> y[i];
  if (k == n - 1) {
    for (int i = 1; i <= k; i++) cout << i << ' ';
    cout << '\n';
    return 0;
  }
  for (int i = 1; i <= n - 1; i++)
    for (int j = i; j <= n; j++) {
      alledges.push_back(
          make_pair(sq(x[i] - x[j]) + sq(y[i] - y[j]), make_pair(i, j)));
    }
  sort((alledges).begin(), (alledges).end());
  reverse((alledges).begin(), (alledges).end());
  distances.push_back(alledges[0].first);
  for (auto& i : alledges)
    if (i.first != distances.back()) distances.push_back(i.first);
  int b = 0;
  int e = ((int)(distances).size()) - 1;
  while (b <= e) {
    int m = (b + e) / 2;
    if (f(distances[m])) {
      b = m + 1;
    } else {
      e = m - 1;
    }
  }
  if (e >= 0) f(distances[e]);
  for (int i = 1; i <= n; i++) {
    if (k > 0 && ans[i]) {
      k--;
      cout << i << ' ';
    }
  }
  for (int i = 1; i <= n; i++)
    if (k > 0 && !ans[i]) {
      k--;
      cout << i << ' ';
    }
  cout << '\n';
}