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 JAVA):

Solution:
import java.io.*;
import java.util.*;
import java.math.*;

public class D {
	static BufferedReader in;
	static StringTokenizer strtok;
	static PrintWriter out;
	
	static int nextInt() throws IOException {
		while (strtok == null || !strtok.hasMoreTokens())
			strtok = new StringTokenizer(in.readLine());
		return Integer.parseInt(strtok.nextToken());
	}

	static class Point implements Comparable<Point> {
		int x, y, cost;
		Point() {
			x = y = cost = 0;
		}
		Point(int x, int y) {
			this.x = x; this.y = y;
		}
		
		Point(int x, int y, int cost) {
			this.x = x; this.y = y; this.cost = cost;
		}
		int dist(Point a) {
			return (x - a.x) * (x - a.x) + (y - a.y) * (y - a.y);
		}

		public int compareTo(Point o) {
			if (cost > o.cost) return 1;
			if (cost < o.cost) return -1;
			return 0;
		}
	};
	
	static Point p[];
	static Point e[];
	static int deg[];
	static boolean dead[];
	static ArrayList<ArrayList<Integer> > g = new ArrayList<ArrayList<Integer> >();
	static int n, k;
	static boolean write = false;
	
	static boolean Dfs(int cur, int k) {
		if (k < 0) return false;
		if (cur == n) { 
			if (write) {
				for (int i = 0; i < n; ++i)
					if (dead[i] || k > 0) {
						out.print((i + 1) + " ");
						if (!dead[i]) --k;
					}
			}
			return true;
		}
		int cnt = 0;
		for (int to : g.get(cur))
			if (!dead[to]) ++cnt;
		
		if (cnt == 0 || dead[cur]) 
			return Dfs(cur + 1, k);
					
		if (cnt != 1) {
			dead[cur] = true;
			if (Dfs(cur + 1, k - 1)) return true;
			dead[cur] = false;
		}
		
		ArrayList<Integer> del = new ArrayList<Integer>();
		for (int to : g.get(cur)) 
			if (!dead[to]) { 
				del.add(to);
				dead[to] = true;
			}
		
		if (Dfs(cur + 1, k - del.size())) 
			return true;
		
		for (int i : del) 
			dead[i] = false;
		return false;
	}
	
	static boolean Ok(int from) {
		++from;
		for (int i = 0; i < n; ++i)
			g.get(i).clear();
		
		for (int i = from; i < e.length; ++i) {
			int u = e[i].x, v = e[i].y;
			g.get(u).add(v);
			g.get(v).add(u);
		}
		
		for (int i = 0; i < n; ++i) {
			deg[i] = g.get(i).size();
			dead[i] = false;
		}
	
		return Dfs(0, k);	
	}
	
	public static void main(String args[]) throws IOException {
		in = new BufferedReader(new InputStreamReader(System.in));
		out = new PrintWriter(System.out);
		
		n = nextInt(); k = nextInt();

		p = new Point[n];
		dead = new boolean[n];
		deg = new int[n];
		
		if (n - k == 1) {
			for (int i = 2; i <= n; ++i)
				out.print(i + " ");
			out.close();
			System.exit(0);
		}
		
		for (int i = 0; i < n; ++i)
			g.add(new ArrayList<Integer>());
		
		for (int i = 0; i < n; ++i)
			p[i] = new Point(nextInt(), nextInt());
		
		e = new Point[(n * (n - 1)) / 2];
		int esz = 0;
		for (int i = 0; i < n; ++i) 
			for (int j = 0; j < i; ++j)
				e[esz++] = new Point(i,j, p[i].dist(p[j]));
		
		Arrays.sort(e);
		int l = -1, r = e.length - 1;
		while (r - 1 > l) {
			int mid = (l + r) >> 1;
			if (Ok(mid)) r = mid; else
			l = mid;
		}
		write = true;
		Ok(r);
		out.close();	
	}
}