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>
#pragma comment(linker, "/STACK:100000000")
using namespace std;
const long double pi = acos(-1.0);
const int N = 1111;
const int INF = (int)2.1e9;
vector<int> adj[N], cur, v;
int d[N][N], x[N], y[N], deg[N], n, k;
bool used[N], dfsused[N];
struct cmp_deg {
  bool operator()(const int& i, const int& j) {
    return (make_pair(-deg[i], i) < make_pair(-deg[j], j));
  }
};
set<int, cmp_deg> s;
int sqr(int x) { return x * x; }
void kill(int v, bool doit) {
  int delta = doit ? -1 : 1;
  if (doit) {
    s.erase(v);
    used[v] = true;
  }
  for (int i = 0; i < ((int)(adj[v]).size()); ++i) {
    if (!used[adj[v][i]]) s.erase(adj[v][i]);
    deg[adj[v][i]] += delta;
    if (!used[adj[v][i]]) s.insert(adj[v][i]);
  }
  if (!doit) {
    s.insert(v);
    used[v] = false;
  }
}
void dfs(int v) {
  dfsused[v] = true;
  cur.push_back(v);
  for (int i = 0; i < ((int)(adj[v]).size()); ++i)
    if (!dfsused[adj[v][i]]) dfs(adj[v][i]);
}
bool checkone(int have) {
  for (int i = 0; i < n; ++i) dfsused[i] = used[i];
  vector<int> v;
  for (int i = 0; i < n; ++i)
    if (!dfsused[i] && (deg[i] <= 1)) {
      cur.clear();
      dfs(i);
      for (int j = 1; j < ((int)(cur).size()); j += 2) v.push_back(cur[j]);
      if (((int)(v).size()) > have) return false;
    }
  for (int i = 0; i < n; ++i)
    if (!dfsused[i]) {
      cur.clear();
      dfs(i);
      for (int j = 0; j < ((int)(cur).size()); j += 2) v.push_back(cur[j]);
      if (((int)(v).size()) > have) return false;
    }
  for (int i = 0; i < ((int)(v).size()); ++i) used[v[i]] = true;
  return true;
}
bool go(int have) {
  int v = *s.begin(), vdeg = deg[v];
  if (vdeg <= 0) return true;
  if (have == 0) return false;
  if (vdeg <= 2) return checkone(have);
  kill(v, true);
  if (go(have - 1)) return true;
  kill(v, false);
  if (vdeg > have) return false;
  vector<int> BE;
  for (int i = 0; i < ((int)(adj[v]).size()); ++i)
    if (!used[adj[v][i]]) {
      kill(adj[v][i], true);
      BE.push_back(adj[v][i]);
    }
  if (go(have - vdeg)) return true;
  for (int i = 0; i < ((int)(BE).size()); ++i) kill(BE[i], false);
  return false;
}
bool check(int q) {
  s.clear();
  v.clear();
  for (int i = 0; i < n; ++i) {
    used[i] = false;
    adj[i].clear();
    for (int j = 0; j < n; ++j)
      if (d[i][j] > q) adj[i].push_back(j);
    deg[i] = ((int)(adj[i]).size());
    s.insert(i);
  }
  return go(k);
}
int main() {
  scanf("%d%d", &n, &k);
  for (int i = 0; i < n; ++i) scanf("%d%d", &x[i], &y[i]);
  for (int i = 0; i < n; ++i)
    for (int j = 0; j < n; ++j) d[i][j] = sqr(x[i] - x[j]) + sqr(y[i] - y[j]);
  int l = -1, r = INF;
  while (l + 1 < r) {
    int q = (l + (long long)r) / 2;
    (check(q) ? r : l) = q;
  }
  assert(check(r));
  fprintf(stderr, "%d\n", r);
  vector<int> v;
  for (int i = 0; i < n; ++i)
    if (used[i]) v.push_back(i);
  for (int i = 0; i < n; ++i)
    if (!used[i] && (((int)(v).size()) < k)) v.push_back(i);
  for (int i = 0; i < ((int)(v).size()); ++i)
    printf("%d%c", v[i] + 1, " \n"[i == ((int)(v).size()) - 1]);
  return 0;
}