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;
int m[1000];
int ud[30];
int fu[30];
int zz[1000];
int gg[1000];
int vnum[1000];
int rc[1000];
int r[1000][1000];
int f[500000];
int s[500000];
int dd[500000];
int f2[500000];
int s2[500000];
int dd2[500000];
int nn[500000];
int mr[500000];
int sz = 0, k, best = 0, n, tmark = 10;
int x[1000];
int y[1000];
int zzots;
bool fucke(int i, int mvc, int md) {
  if (i >= mvc) {
    int t = 0;
    while (md > 0) {
      if (!m[t]) {
        m[t] = 1;
        ud[--md] = t;
      }
      ++t;
    }
    return true;
  }
  int v = vnum[i];
  if ((zz[v] == 0) || (m[v])) {
    return fucke(i + 1, mvc, md);
  }
  if (md == 0) return false;
  if (zz[v] != 1) {
    for (int j = 0; j < rc[v]; ++j) {
      --zz[r[v][j]];
    }
    m[v] = 1;
    ud[md - 1] = v;
    if (v == 626) {
      clog << "huiin " << endl;
    }
    if (fucke(i + 1, mvc, md - 1)) return true;
    if (v == 626) {
      clog << "huiout " << endl;
    }
    m[v] = 0;
    for (int j = 0; j < rc[v]; ++j) {
      ++zz[r[v][j]];
    }
  }
  if (zz[v] <= md) {
    int omd = md;
    for (int j = 0; j < rc[v]; ++j) {
      if (!m[r[v][j]]) {
        int dd = r[v][j];
        if (dd == 626) {
          clog << "pizdain " << endl;
        }
        for (int k = 0; k < rc[dd]; ++k) {
          --zz[r[dd][k]];
        }
        ud[--md] = dd;
        m[dd] = 1;
      }
    }
    if (fucke(i + 1, mvc, md)) return true;
    while (omd > md) {
      int dd = ud[--omd];
      if (dd == 626) {
        clog << "pizdaout" << endl;
      }
      for (int k = 0; k < rc[dd]; ++k) {
        ++zz[r[dd][k]];
      }
      m[dd] = 0;
    }
  }
  return false;
}
bool check(int x) {
  ++tmark;
  memset(zz, 0, sizeof(zz));
  memset(m, 0, sizeof(m));
  int uk = k;
  for (int i = 0; i < x; ++i) {
    ++zz[f2[i]];
    ++zz[s2[i]];
    if ((zz[f2[i]] > k) && (!m[f2[i]])) {
      if (uk == 0) return false;
      ud[--uk] = f2[i];
      m[f2[i]] = 1;
    }
    if ((zz[s2[i]] > k) && (!m[s2[i]])) {
      if (uk == 0) return false;
      ud[--uk] = s2[i];
      m[s2[i]] = 1;
    }
  }
  while (1) {
    bool bo = false;
    for (int i = 0; i < x; ++i) {
      if ((m[s2[i]] || m[f2[i]]) && (mr[i] != tmark)) {
        --zz[f2[i]];
        --zz[s2[i]];
        mr[i] = tmark;
      }
    }
    for (int i = 0; i < x; ++i) {
      if (!(m[s2[i]] || m[f2[i]])) {
        if (zz[f2[i]] == 1) {
          if (uk == 0) return false;
          bo = true;
          ud[--uk] = s2[i];
          m[s2[i]] = 1;
        } else if (zz[s2[i]] == 1) {
          if (uk == 0) return false;
          bo = true;
          ud[--uk] = f2[i];
          m[f2[i]] = 1;
        }
      }
    }
    if (!bo) break;
  }
  int uk2 = 0;
  memset(zz, 0, sizeof(zz));
  memset(rc, 0, sizeof(rc));
  memset(gg, 0, sizeof(gg));
  int vc = 0;
  for (int i = 0; i < x; ++i) {
    if ((!(m[s2[i]])) && (!(gg[s2[i]]))) {
      gg[s2[i]] = 1;
      vnum[vc++] = s2[i];
    }
    if ((!(m[f2[i]])) && (!(gg[f2[i]]))) {
      gg[f2[i]] = 1;
      vnum[vc++] = f2[i];
    }
    if (!(m[s2[i]] || m[f2[i]])) {
      r[s2[i]][rc[s2[i]]++] = f2[i];
      r[f2[i]][rc[f2[i]]++] = s2[i];
      ++zz[f2[i]];
      ++zz[s2[i]];
    }
  }
  bool b = (fucke(0, vc, uk));
  if ((b) && (x > best)) {
    best = x;
    memcpy(fu, ud, 120);
  }
  return b;
}
bool lss(int i, int j) { return (dd2[i] > dd2[j]); }
int main() {
  cin >> n >> k;
  for (int i = 0; i < n; ++i) cin >> x[i] >> y[i];
  for (int i = 0; i < n; ++i)
    for (int j = i + 1; j < n; ++j) {
      f2[sz] = i;
      s2[sz] = j;
      dd2[sz] = (x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]);
      nn[sz] = sz;
      ++sz;
    }
  sort(nn, nn + sz, lss);
  for (int i = 0; i < sz; ++i) {
    f[i] = f2[nn[i]];
    s[i] = s2[nn[i]];
    dd[i] = dd2[nn[i]];
  }
  memcpy(f2, f, sizeof(f));
  memcpy(s2, s, sizeof(s));
  int l = 0, r = sz;
  while (r - l > 1) {
    int t = (l + r) / 2;
    if (check(t))
      l = t;
    else
      r = t;
  }
  clog << best << endl;
  for (int i = 0; i < k; ++i) cout << fu[i] + 1 << " ";
  cout << endl;
  return 0;
}