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;
struct edge {
  long long d;
  int a, b;
};
bool operator<(const edge &a, const edge &b) { return a.d > b.d; }
int n, k;
vector<int> res;
struct Graph {
  int vertex_n;
  vector<int> deg;
  struct node {
    int v;
    node *next, *prev;
    node() {}
    node(int v) : v(v) {}
  };
  vector<node> by_deg_st, by_deg;
  node *edges;
  int edges_i;
  vector<node> edges_st;
  vector<int> log, marked;
  int marked_n;
  void connect(node *a, node *b) {
    a->next = b;
    b->prev = a;
  }
  void add_node(node *list, node *v) {
    connect(list->prev, v);
    connect(v, list);
  }
  void del_node(node *v) { connect(v->prev, v->next); }
  void fix_deg(int id) {
    node *v = &by_deg[id];
    del_node(v);
    add_node(&by_deg_st[deg[id]], v);
  }
  Graph(int n, int en)
      : vertex_n(n),
        deg(n, 0),
        by_deg_st(n),
        by_deg(n),
        edges(new node[en * 2]),
        edges_i(0),
        edges_st(n),
        marked(n, 0),
        marked_n(0) {
    for (int i = 0; i < n; i++) {
      by_deg_st[i].next = by_deg_st[i].prev = &by_deg_st[i];
      edges_st[i].next = edges_st[i].prev = &edges_st[i];
    }
    for (int i = 0; i < n; i++) {
      by_deg[i].v = i;
      add_node(&by_deg_st[0], &by_deg[i]);
    }
  }
  void log_del_edge(int x) { log.push_back(x + 1); }
  void log_del_vertex(int x) { log.push_back(-(x + 1)); }
  void log_checkpoint(void) { log.push_back(0); }
  void add_edge(int fwd) {
    int rev = fwd ^ 1, b = edges[fwd].v, a = edges[rev].v;
    deg[a]++;
    deg[b]++;
    fix_deg(a);
    fix_deg(b);
    add_node(&edges_st[a], &edges[fwd]);
    add_node(&edges_st[b], &edges[rev]);
  }
  void new_edge(int a, int b) {
    int fwd = edges_i;
    edges[edges_i++].v = b;
    edges[edges_i++].v = a;
    add_edge(fwd);
  }
  void del_vertex(int v) {
    node *end = &edges_st[v];
    for (node *end = &edges_st[v], *i = end->next; i != end; i = i->next) {
      int id = i - edges;
      log_del_edge(id);
      del_node(i);
      del_node(&edges[id ^ 1]);
      deg[i->v]--;
      deg[v]--;
      fix_deg(i->v);
    }
    log_del_vertex(v);
    vertex_n--;
    del_node(&by_deg[v]);
  }
  void log_restore(void) {
    int x;
    while ((x = log.back()) != 0) {
      log.pop_back();
      if (x < 0) {
        x = -x - 1;
        add_node(&by_deg_st[0], &by_deg[x]);
        vertex_n++;
        if (marked[x]) {
          marked[x] = 0;
          marked_n--;
        }
      } else {
        x = x - 1;
        add_edge(x);
      }
    }
    log.pop_back();
  }
  void del_01() {
    while (true) {
      node *i = &by_deg_st[1];
      if (i->next == i) {
        break;
      }
      int v = i->next->v, u = edges_st[v].next->v;
      marked[u] = 1;
      marked_n++;
      del_vertex(u);
    }
    for (node *end = &by_deg_st[0], *i = end->next; i != end; i = i->next) {
      del_vertex(i->v);
    }
  }
  void dump_result() {
    res.clear();
    for (int i = 0; i < n; i++) {
      if (marked[i]) {
        res.push_back(i);
      }
    }
  }
  bool solve(int max_deg, int k) {
    del_01();
    if (k < marked_n) {
      return false;
    }
    if (vertex_n == 0) {
      dump_result();
      return true;
    }
    while (by_deg_st[max_deg].next == &by_deg_st[max_deg]) {
      max_deg--;
    }
    if ((max_deg + 1) * (k - marked_n) < vertex_n) {
      return false;
    }
    int v = by_deg_st[max_deg].next->v;
    log_checkpoint();
    marked[v] = 1;
    marked_n++;
    del_vertex(v);
    if (solve(max_deg, k)) {
      return true;
    }
    log_restore();
    if (k - marked_n > max_deg && max_deg > 2) {
      log_checkpoint();
      for (node *end = &edges_st[v], *i = end->next; i != end; i = i->next) {
        int u = i->v;
        marked[u] = 1;
        marked_n++;
        del_vertex(u);
      }
      if (solve(max_deg, k)) {
        return true;
      }
      log_restore();
    }
    return false;
  }
  ~Graph() { delete[] edges; }
};
bool can(const vector<edge> &edges, int edges_n, int k) {
  Graph g(n, edges_n);
  for (int i = 0; i < edges_n; i++) {
    g.new_edge(edges[i].a, edges[i].b);
  }
  return g.solve(n - 1, k);
}
int main(void) {
  scanf("%d%d", &n, &k);
  vector<int> xs(n), ys(n);
  for (int i = 0; i < n; i++) {
    scanf("%d%d", &xs[i], &ys[i]);
  }
  int edges_n = n * (n - 1) / 2, edges_i = 0;
  vector<edge> edges(edges_n);
  for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
      edges[edges_i].d = (long long)(xs[i] - xs[j]) * (xs[i] - xs[j]) +
                         (long long)(ys[i] - ys[j]) * (ys[i] - ys[j]);
      edges[edges_i].a = i;
      edges[edges_i++].b = j;
    }
  }
  sort(edges.begin(), edges.end());
  int l = 0, r = edges_n + 1;
  while (l + 1 < r) {
    int c = (l + r) / 2;
    if (can(edges, c, k)) {
      l = c;
    } else {
      r = c;
    }
  }
  can(edges, l, k);
  vector<int> mask(n, 0);
  for (int i = 0; i < (int)res.size(); i++) {
    mask[res[i]] = 1;
  }
  int left = k - (int)res.size();
  for (int i = 0; i < n && left > 0; i++) {
    if (!mask[i]) {
      mask[i] = 1;
      left--;
    }
  }
  for (int i = 0; i < n; i++) {
    if (mask[i]) {
      printf("%d ", i + 1);
    }
  }
  return 0;
}