Polyline Simplification

Mapping applications represent the boundaries of countries and cities as polylines, which are connected sequences of line segments. Fine details have to be shown when the user zooms in, so such a polyline often contains a very large number of segments. When the user zooms out, those details do not matter, and processing and drawing a polyline with that many segments is wasteful. This problem uses one polyline simplification algorithm that approximates the original polyline with a polyline that has fewer segments.

A polyline with $n$ segments is described by $n + 1$ points $p_0 = (x_0, y_0), \dots, p_n = (x_n, y_n)$, where the $i$th segment joins $p_{i-1}$ and $p_i$. Removing an interior point $p_i$ ($1 \le i \le n - 1$) simplifies the polyline: the segments $p_{i-1}p_i$ and $p_i p_{i+1}$ are replaced by the single segment $p_{i-1}p_{i+1}$. Choose the point to remove like this. For every interior point $p_i$, compute the area of the triangle formed by $p_{i-1}$, $p_i$ and $p_{i+1}$ (the area is $0$ when the three points are colinear), and remove the point whose triangle has the smallest area. When several points have the smallest area, remove the one with the smallest index in the original polyline. Apply the same rule to the resulting polyline again, until the desired number $m$ of segments is left.

The figure below shows one step.

The original polyline is at the top. In the middle, the area of the triangle formed by $p_2$, $p_3$ and $p_4$ is measured, and $p_3$ is removed when that area is the smallest among all such triangles. The bottom shows the polyline after $p_3$ is removed.

The first line contains two integers $n$ ($2 \le n \le 200\,000$) and $m$ ($1 \le m < n$). Each of the next $n + 1$ lines describes one point, giving $p_0$ through $p_n$ in order. A line holds the $x$ and $y$ coordinates of the point, both integers between $-5000$ and $5000$ inclusive. The points are strictly increasing in lexicographic order. That is, for every $0 \le i < n$, either $x_i < x_{i+1}$, or $x_i = x_{i+1}$ and $y_i < y_{i+1}$.

Print $n - m$ lines. On the $k$th line print the index of the point removed in the $k$th step of the algorithm above. Use the index the point has in the original polyline.