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 N = 1002;
const int NN = 1000010;
bool kind;
int i, mid, j, l, r, kk, n, tt, tot, sp;
int ki[N], x[N], y[N], du[N], dd[NN], ev[NN], pre[NN], la[N];
int an[N];
int e[N][N];
void remove(int v) {
  if ((++ki[v]) != 1) return;
  sp++;
  for (int j = la[v]; j; j = pre[j])
    if (!ki[ev[j]]) du[ev[j]]--, du[v]--;
}
void resume(int v) {
  if ((--ki[v]) != 0) return;
  sp--;
  for (int j = la[v]; j; j = pre[j])
    if (!ki[ev[j]]) du[ev[j]]++, du[v]++;
}
bool dfs(int i) {
  if (sp > kk) return false;
  if (i > n) {
    an[0] = 0;
    an[n + 1] = n + 1;
    for (int j = 1; j <= n; j++)
      if (ki[j])
        an[++an[0]] = j;
      else
        an[--an[n + 1]] = j;
    return true;
  }
  if (du[i] == 0) return dfs(i + 1);
  if (du[i] > 1) {
    remove(i);
    if (dfs(i + 1)) return true;
    resume(i);
  }
  for (int j = la[i]; j; j = pre[j]) remove(ev[j]);
  if (dfs(i + 1)) return true;
  for (int j = la[i]; j; j = pre[j]) resume(ev[j]);
  return false;
}
void add(int a, int b) {
  ++du[a];
  ev[++tot] = b;
  pre[tot] = la[a];
  la[a] = tot;
}
bool ck(int li) {
  tot = 0;
  for (int i = 1; i <= n; i++) la[i] = du[i] = ki[i] = 0;
  for (int i = 1; i <= n; i++)
    for (int j = i + 1; j <= n; j++)
      if (e[i][j] > li) add(i, j), add(j, i);
  sp = 0;
  return dfs(1);
}
int main() {
  scanf("%d%d", &n, &kk);
  for (int i = 1; i <= n; i++) scanf("%d%d", &x[i], &y[i]);
  dd[0] = 0;
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++)
      e[i][j] = (x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]),
      dd[++dd[0]] = e[i][j];
  sort(dd + 1, dd + 1 + dd[0]);
  l = 0;
  r = dd[0] - 1;
  dd[0] = 0;
  while (l < r) {
    mid = (l + r) / 2;
    if (ck(dd[mid]))
      r = mid;
    else
      l = mid + 1;
  }
  kind = ck(dd[r]);
  for (int i = 1; i <= kk; i++) printf("%d ", an[i]);
}