Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

D. Minimum Diameter

time limit per test

1.5 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou 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 *x*_{i}, *y*_{i} (0 ≤ *x*_{i}, *y*_{i} ≤ 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

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Feb/22/2020 07:46:30 (f3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|