Problem J
A Horse Shoe-In

With Twilight Sparkle making preparations to ascend the throne as the new ruler of Equestria, she has resigned from her post as the headmare of the School of Friendship, appointing former guidance counselor Starlight Glimmer in her place.

Knowing that the work will be too much for her to handle alone, Starlight wishes to hire a vice headmare to help her. She decides to place posters advertising the position around the lobby of the school.

Figure 1: Illustration by Kyle Coate.

The lobby can be represented as a strictly convex polygon with $N$ vertices. (Recall that a strictly convex polygon is a polygon where all internal angles are strictly less than $180^\circ $.) Posters can be placed only on the vertices of this polygon, and at most one poster can be placed on each vertex.

A point strictly inside the polygon is called an interior point. An interior point is called a covered point if there exist three vertices having posters such that this point is strictly within the triangle formed by those three vertices. Covered points are relevant because ponies standing on a covered point are more likely to see a poster and apply.

Figure 2: Illustration of Sample Input 1.

Starlight was about to put up the posters when her best friend Trixie expressed interest in the position. It would obviously not be proper to give her the position directly—that would be brazen nepotism—however, she still feels that she would probably be much more productive working alongside someone she likes. Hence, she decides to give Trixie a leg up by reducing the competition; by strategically placing the posters such that the proportion of interior points that are covered is minimized, she can ensure that fewer ponies see the posters, resulting in fewer applicants and a higher chance that her best friend is the best candidate!

Of course, Starlight still needs to place enough posters to make sure at least some other ponies are aware of the opening and apply. She decides to place exactly $K$ posters around the lobby.

Help her decide where to place the posters such that the proportion of interior points that are covered is minimized!

Input

The first line of input contains two integers, $N$ ($3 \leq N \leq 4\, 000$) and $K$ ($\max (1, N-80) \leq K \leq N$), the number of vertices in the polygon and the number of posters Starlight must place, respectively.

The next $N$ lines of input contain the descriptions of the vertices. In particular, the $i^\text {th}$ of these lines contains two integers $X_ i$ and $Y_ i$ ($-10^9 \leq X_ i, Y_ i \leq 10^9$), denoting that the $i^\text {th}$ vertex is at position $(X_ i, Y_ i)$.

The vertices are given in clockwise order. It is guaranteed that there are no two vertices at the same position, and the polygon is strictly convex.

Output

Output $K$ integers $d_1, d_2, \dots , d_ K$ ($1 \leq d_ i \leq N$), denoting the vertices that Starlight should place the posters on.

All $d_ i$ should be distinct and placing the posters on these vertices should, among all such placements, result in the minimum proportion of interior points being covered. You can output the vertices in any order.

If there are multiple correct answers, you can output any of them.

6 4
0 0
-1 4
0 5
4 4
5 0
4 -1

2 3 5 6

4 3
-100 100
100 100
100 -100
-100 -100

1 2 3