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 MAXN = 1005;
int n, m;
int x[MAXN], y[MAXN];
bool g[MAXN][MAXN];
int ans[MAXN];
int en, e1[30005], e2[30005];
bool u[MAXN], exi[MAXN];
int d[MAXN];
int Num;
bool flag;
int c[MAXN][MAXN], cn[MAXN];
int Tm = 0;
inline void Add(int p) {
  u[p] = true;
  for (int i = 1; i <= cn[p]; i++) d[c[p][i]]--;
}
inline void Del(int p) {
  u[p] = false;
  for (int i = 1; i <= cn[p]; i++) d[c[p][i]]++;
}
void dfs(int p, int k) {
  if (flag || k > m) return;
  if (p > n) {
    flag = true;
    int ansn = 0;
    for (int i = 1; i <= n; i++)
      if (u[i]) ans[++ansn] = i;
    for (int i = 1; i <= n; i++)
      if (!u[i] && ansn != m) ans[++ansn] = i;
    return;
  }
  if (u[p] || d[p] == 0) {
    dfs(p + 1, k);
    return;
  }
  bool f = false;
  for (int i = 1; i <= cn[p]; i++)
    if (!u[c[p][i]] && c[p][i] < p) {
      f = true;
      break;
    }
  if (!f) {
    int S[55], sn = 0;
    for (int i = 1; i <= cn[p]; i++)
      if (!u[c[p][i]]) {
        Add(c[p][i]);
        k++;
        S[++sn] = c[p][i];
      }
    dfs(p + 1, k);
    while (sn) Del(S[sn--]), k--;
  }
  if (f || d[p] != 1) {
    Add(p);
    dfs(p + 1, k + 1);
    Del(p);
  }
}
bool chk(int mid) {
  memset(exi, 0, sizeof(exi));
  memset(d, 0, sizeof(d));
  memset(u, 0, sizeof(u));
  memset(cn, 0, sizeof(cn));
  en = 0;
  Num = 0;
  for (int i = 1; i <= n; i++)
    for (int j = 1; j < i; j++)
      if (en <= n * m) {
        int dis = (x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]);
        if (dis > mid) {
          d[i]++;
          d[j]++;
          en++;
          e1[en] = j;
          e2[en] = i;
          cn[i]++;
          c[i][cn[i]] = j;
          cn[j]++;
          c[j][cn[j]] = i;
          if (!exi[i]) Num++;
          if (!exi[j]) Num++;
          exi[i] = true;
          exi[j] = true;
        }
      }
  if (en > n * m) return false;
  if (Num <= m) {
    int ansn = 0;
    for (int i = 1; i <= n; i++)
      if (exi[i]) ans[++ansn] = i;
    for (int i = 1; i <= n; i++)
      if (!exi[i] && ansn != m) ans[++ansn] = i;
    return true;
  }
  int s = 0;
  bool t = true;
  while (t) {
    t = false;
    for (int i = 1; i <= n; i++)
      if (d[i] > m && !u[i]) {
        Add(i);
        s++;
        t = true;
      }
    for (int i = 1; i <= n; i++)
      if (d[i] == 1 && !u[i]) {
        t = true;
        for (int j = 1; j <= cn[i]; j++)
          if (!u[c[i][j]]) {
            s++;
            Add(c[i][j]);
            break;
          }
      }
  }
  Tm = 0;
  flag = false;
  dfs(1, s);
  return flag;
}
int di[MAXN * MAXN / 2], di2[MAXN * MAXN / 2];
int nm = 0, nm2 = 0;
int main() {
  srand(time(0));
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) scanf("%d%d", &x[i], &y[i]);
  for (int i = 1; i <= n; i++)
    for (int j = i + 1; j <= n; j++)
      di[++nm] = (x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]);
  di[0] = 0;
  sort(di, di + nm + 1);
  for (int i = 1; i <= nm; i++)
    if (di[i] != di[i - 1]) di2[++nm2] = di[i];
  unsigned l = 0, r = nm2 + 1;
  while (l < r) {
    int mid = (l + r) >> 1;
    if (chk(di2[mid]))
      r = mid;
    else
      l = mid + 1;
  }
  for (int i = 1; i <= m; i++) printf("%d ", ans[i]);
  printf("\n");
  return 0;
}