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;
void task();
int main() {
  srand(time(0));
  task();
  return 0;
}
const int N = 1e3 + 10;
struct Segment {
  long long int dist;
  int a;
  int b;
  friend bool operator<(const Segment &p1, const Segment &p2) {
    return p1.dist > p2.dist;
  }
};
int n, k;
long long int x[N];
long long int y[N];
Segment segments[N * N];
int used[N];
int m;
vector<int> ans;
inline long long int sqr(long long int x) { return x * x; }
inline long long int dist(long long int x1, long long int y1, long long int x2,
                          long long int y2) {
  return sqr(x1 - x2) + sqr(y1 - y2);
}
struct G {
  vector<pair<int, int> > ribs;
  set<int> vals;
  map<int, int> conv;
  map<int, int> rconv;
  int n;
  vector<vector<int> > g;
  vector<int> color;
  vector<int> mt;
  vector<int> used;
  vector<int> in_matching;
  void add(int a, int b) {
    vals.insert(a);
    vals.insert(b);
    ribs.push_back(pair<int, int>{a, b});
  }
  void dfs(int v, int t) {
    if (color[v] != -1) {
      assert(t == color[v]);
      return;
    }
    color[v] = t;
    for (int to : g[v]) dfs(to, (t + 1) % 2);
  }
  void build_graph() {
    n = 0;
    for (int x : vals) {
      conv[x] = n;
      rconv[n] = x;
      ++n;
    }
    g.resize(n);
    for (pair<int, int> rib : ribs) {
      g[conv[rib.first]].push_back(conv[rib.second]);
      g[conv[rib.second]].push_back(conv[rib.first]);
    }
    color.resize(n, -1);
    for (int i = 0; i < n; ++i)
      if (color[i] == -1) dfs(i, 0);
    for (int i = 0; i < n; ++i)
      if (color[i]) g[i].clear();
  }
  bool try_kuhn(int v, int step) {
    if (used[v]) return false;
    used[v] = 1;
    for (int to : g[v])
      if (mt[to] == -1 || try_kuhn(mt[to], step)) {
        mt[to] = v;
        in_matching[v] = 1;
        return true;
      }
    return false;
  }
  int kuhn() {
    mt.assign(n, -1);
    in_matching.assign(n, 0);
    int cnt = 0;
    for (int i = 0; i < n; ++i) {
      used.assign(n, 0);
      cnt += try_kuhn(i, i);
      if (cnt > 30) return cnt;
    }
    return cnt;
  }
  set<pair<int, int> > bad;
  void go(int v) {
    if (used[v]) return;
    used[v] = 1;
    for (int to : g[v])
      if (bad.count(pair<int, int>{v, to}) == 0) {
        used[to] = 1;
        if (mt[to] != -1) go(mt[to]);
      }
  }
  vector<int> calc() {
    build_graph();
    int cnt = 0;
    if ((cnt = kuhn()) > 30) return vector<int>(31);
    used.assign(n, 0);
    vector<int> res;
    for (int i = 0; i < n; ++i)
      if (mt[i] != -1) bad.insert(pair<int, int>{mt[i], i});
    for (int i = 0; i < n; ++i)
      if (color[i] == 0 && !in_matching[i]) {
        go(i);
      }
    for (int i = 0; i < n; ++i)
      if ((color[i] == 0 && !used[i]) || (color[i] == 1 && used[i]))
        res.push_back(rconv[i]);
    return res;
  }
};
void task() {
  scanf("%d %d", &n, &k);
  for (int i = 0; i < n; ++i) scanf("%I64d %I64d", &x[i], &y[i]);
  for (int i = 0; i < n; ++i)
    for (int j = i + 1; j < n; ++j)
      segments[m++] = Segment{dist(x[i], y[i], x[j], y[j]), i, j};
  sort(segments, segments + m);
  memset(used, -1, sizeof(used));
  for (int i = 0; i < m; ++i) {
    if (clock() * 1.0 / CLOCKS_PER_SEC > 0.55) break;
    Segment &s = segments[i];
    vector<int> res;
    for (int j = 0; j < n; ++j)
      if (dist(x[s.a], y[s.a], x[j], y[j]) > s.dist ||
          dist(x[s.b], y[s.b], x[j], y[j]) > s.dist) {
        used[j] = i;
        res.push_back(j);
      }
    if (((int)((res).size())) > k) continue;
    G g;
    for (int j = 0; j < m && segments[j].dist > s.dist; ++j)
      if (used[segments[j].a] != i && used[segments[j].b] != i && i != j) {
        g.add(segments[j].a, segments[j].b);
      }
    vector<int> r = g.calc();
    if (((int)((r).size())) + ((int)((res).size())) <= k) {
      ans = r;
      for (int x : res) ans.push_back(x);
    }
  }
  set<int> ss;
  for (int x : ans) ss.insert(x);
  for (int i = 0; ((int)((ss).size())) < k; ++i)
    if (ss.count(i) == 0) ss.insert(i);
  for (int x : ss) printf("%d ", x + 1);
}