地图应用通常将国家、城市等的边界表示为折线，即相连的线段序列。由于在用户放大地图时需要显示精细的细节，这些折线通常包含非常多的线段。然而，当用户缩小地图时，这些精细的细节就不再重要，处理和绘制包含如此多线段的折线是十分浪费的。在本题中，我们考虑一种特定的折线简化算法，旨在用包含较少线段的折线来逼近原始折线。

一条包含 $n$ 条线段的折线由 $n + 1$ 个点 $p_0 = (x_0, y_0), \dots, p_n = (x_n, y_n)$ 描述，其中第 $i$ 条线段为 $p_{i-1}p_i$。折线可以通过移除一个内部点 $p_i$ ($1 \le i \le n - 1$) 来简化，从而将线段 $p_{i-1}p_i$ 和 $p_i p_{i+1}$ 替换为线段 $p_{i-1}p_{i+1}$。为了选择要移除的点，我们计算由 $p_{i-1}$、$p_i$ 和 $p_{i+1}$ 构成的三角形的面积（如果三点共线，则面积为 $0$），并选择使三角形面积最小的点 $p_i$。如果存在多个点的三角形面积相同，则选择索引最小的点。这一操作可以重复应用于简化后的折线，直到达到目标线段数 $m$。

考虑下面的例子。

原始折线如上图所示。考虑由 $p_2$、$p_3$ 和 $p_4$ 构成的三角形的面积（中图），如果该面积在所有此类三角形中最小，则移除 $p_3$。移除 $p_3$ 后的折线如下底图所示。

输入格式

输入的第一行包含两个整数 $n$ ($2 \le n \le 200\,000$) 和 $m$ ($1 \le m < n$)。

接下来的 $n + 1$ 行指定 $p_0, \dots, p_n$。每个点由其 $x$ 和 $y$ 坐标给出，坐标为 $-5000$ 到 $5000$ 之间的整数（包含边界）。

你可以假设给定的点在字典序上是严格递增的。也就是说，对于所有 $0 \le i < n$，有 $x_i < x_{i+1}$，或者 $x_i = x_{i+1}$ 且 $y_i < y_{i+1}$。

输出格式

在第 $k$ 行输出在上述算法的第 $k$ 步中被移除的点的索引（使用原始折线中的索引）。

样例

输入样例 1

10 7
0 0
1 10
2 20
25 17
32 19
33 5
40 10
50 13
65 27
75 22
85 17

输出样例 1

1
9
6