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 static java.lang.Math.*;
import static java.lang.System.currentTimeMillis;
import static java.lang.System.exit;
import static java.lang.System.arraycopy;
import static java.util.Arrays.sort;
import static java.util.Arrays.binarySearch;
import static java.util.Arrays.fill;
import java.util.*;
import java.io.*;

public class Main {

	public static void main(String[] args) throws IOException {
		try {
			if (new File("input.txt").exists())
				System.setIn(new FileInputStream("input.txt"));
		} catch (SecurityException e) {
		}
		new Thread(null, new Runnable() {
			public void run() {
				try {
					new Main().run();
				} catch (IOException e) {
					e.printStackTrace();
					exit(999);
				}
			}
		}, "kek", 1 << 23).start();
	}

	BufferedReader in;
	PrintWriter out;
	StringTokenizer st = new StringTokenizer("");

	private void run() throws IOException {
		in = new BufferedReader(new InputStreamReader(System.in));
		out = new PrintWriter(System.out);
		solve();
		in.close();
		out.close();
	}
	int n, k;
	int x[];
	int y[];
	Edge eg[];
	int cnt = 0;
	int deg[];
	int used[];
	int tick = 1;
	MultiList g;
	private void solve() throws IOException{
		n = nextInt();
		k = nextInt();
		x = new int[n];
		y = new int[n];
		eg = new Edge[n * (n - 1) / 2];
		g = new MultiList(n, n * (n - 1));
		deg = new int[n];
		used = new int[n];
		for(int i = 0; i < n; i++){
			x[i] = nextInt();
			y[i] = nextInt();
		}
		for(int i = 0; i < n; i++)
			for(int j = i + 1; j < n; j++)
				eg[cnt++] = new Edge(i, j);
		chk(cnt == eg.length);
		sort(eg);
		
		int le = 0;
		int ri = cnt;
		int ret = le;
		while(le <= ri){
			int mid = (le + ri) >> 1;
			if(check(mid)){
				le = mid + 1;
				ret = max(ret, mid);
			} else 
				ri = mid - 1;
		}
		check(ret);
		boolean fst = true;
		for(int i = 0; i < n; i++){
			if(used[i] != tick) continue;
			if(!fst) out.print(" ");
			fst = false;
			out.print((i + 1));
		}
		out.println();
	}
	
	
	private boolean check(int count) {
		tick++;
//		System.err.println(count);
		buildGraph(count);
		return dfs(0, k);
	}

	int stack[] = new int[5000];
	int stp = 0;
	
	private boolean dfs(int pos, int free) {
		
		if(free < 0) return false;
		if(pos == n)
			return true;
		if(deg[pos] == 0 || used[pos] == tick)
			return dfs(pos + 1, free);
		
		if(deg[pos] == 1){
			int last = -1;
			for(int j = g.head[pos]; j != 0; j = g.next[j])
				if(used[g.vert[j]] != tick){
					chk(last == -1);
					last = g.vert[j];
				}
			remove(last);
			if(dfs(pos + 1, free - 1)){
				return true;
			}
			restore(last);
			return false;
		} else {
			int cur = stp;
			// remove neigh
			for(int j = g.head[pos]; j != 0; j = g.next[j])
				if(used[g.vert[j]] != tick)
					stack[stp++] = g.vert[j];
			for(int i = cur; i < stp; i++)
				remove(stack[i]);
			if(dfs(pos + 1, free - (stp - cur))){
				return true;
			
			}
			for(int i = cur; i < stp; i++)
				restore(stack[i]);
			stp = cur;
			//remove self
			remove(pos);
			if(dfs(pos + 1, free - 1)){
				return true;
			}
			restore(pos);
			return false;
		}
	}


	private void restore(int v) {
		for(int j = g.head[v]; j != 0; j = g.next[j])
			deg[g.vert[j]]++;
		used[v] = tick - 1;		
	}


	private void remove(int v) {
		for(int j = g.head[v]; j != 0; j = g.next[j])
			deg[g.vert[j]]--;
		used[v] = tick;
	}


	private void buildGraph(int count) {
		fill(deg, 0);
		g.clear();
		for(int i = 0; i < count; i++){
			Edge e = eg[cnt - 1 - i];
			g.add(e.a, e.b);
			g.add(e.b, e.a);
			deg[e.a]++;
			deg[e.b]++;
		}
	}


	private void chk(boolean b) {
		if(!b) throw new RuntimeException();
	}

	class MultiList{
		int[] head, vert, next;
		int cnt;
		public MultiList(int h, int s) {
			s++;
			cnt = 1;
			head = new int[h];
			vert = new int[s];
			next = new int[s];
		}
		void add(int h, int v){
//			System.err.println(h + " -> " + v);
			vert[cnt] = v;
			next[cnt] = head[h];
			head[h] = cnt++;
		}
		void clear(){
			cnt = 1;
			fill(head, 0);
		}
	}

	class Edge implements Comparable<Edge>{
		int a, b;
		int dist;
		public Edge(int aa, int bb) {
			a = aa;
			b = bb;
			dist = dist(a, b);
		}
		@Override
		public int compareTo(Edge e) {
			return dist - e.dist;
		}
	}
	int dist(int i, int j){
		return sqr(x[i] - x[j]) + sqr(y[i] - y[j]);
	}
	int sqr(int x){
		return x * x;
	}
	String nextToken() throws IOException {
		while (!st.hasMoreTokens())
			st = new StringTokenizer(in.readLine());
		return st.nextToken();
	}
	int nextInt() throws IOException {
		return Integer.parseInt(nextToken());
	}
	long nextLong() throws IOException {
		return Long.parseLong(nextToken());
	}
	double nextDouble() throws IOException {
		return Double.parseDouble(nextToken());
	}
	String nextLine() throws IOException {
		st = new StringTokenizer("");
		return in.readLine();
	}
	boolean EOF() throws IOException {
		while (!st.hasMoreTokens()) {
			String s = in.readLine();
			if (s == null)
				return true;
			st = new StringTokenizer(s);
		}
		return false;
	}
}