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 tot, s, e, mid, n, x[1011], y[1011], dl[1011], d[1011], who[1011], i, j, k;
int con[1011][1011];
bool used[1011];
bool dfs(int now, int left) {
  int i, need = 0;
  if (now > n) {
    for (i = 1; i <= n; i++)
      if (d[i] > 0) used[i] = true;
    return true;
  }
  if (d[now] > 0) return dfs(now + 1, left);
  for (i = 1; i <= con[now][0]; i++)
    if (d[con[now][i]] == 0) need++;
  if (need <= left) {
    for (i = 1; i <= con[now][0]; i++) d[con[now][i]]++;
    if (dfs(now + 1, left - need)) return true;
    for (i = 1; i <= con[now][0]; i++) d[con[now][i]]--;
  }
  if (left > 0 && need > 1) {
    d[now]++;
    if (dfs(now + 1, left - 1)) return true;
    d[now]--;
  }
  return false;
}
bool check(int ans) {
  tot = 0;
  memset(d, 0, sizeof(d));
  memset(used, 0, sizeof(used));
  for (i = 1; i <= n; i++) con[i][0] = 0;
  int i, j;
  for (i = 1; i <= n; i++)
    for (j = i + 1; j <= n; j++)
      if ((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]) > ans) {
        con[i][++con[i][0]] = j;
        con[j][++con[j][0]] = i;
      }
  return dfs(1, k);
}
int main() {
  scanf("%d%d", &n, &k);
  for (i = 1; i <= n; i++) scanf("%d%d", &x[i], &y[i]);
  s = 0;
  e = 1 << 30;
  while (s != e) {
    mid = (s + e) / 2;
    if (check(mid))
      e = mid;
    else
      s = mid + 1;
  }
  check(s);
  for (i = 1; i <= n; i++)
    if (used[i]) k--;
  for (i = 1; i <= n; i++)
    if (used[i])
      printf("%d ", i);
    else if (k)
      k--, printf("%d ", i);
  return 0;
}