Optimized Royal Route

In a kingdom of an infinite flat two‐dimensional plane, there are n locations where people gather. The wise king originally planned to visit these locations in order, forming a polygonal chain p: p₁ → p₂ → … → p_n. However, because the king is old, his assistants want to skip some locations while ensuring that the king does not miss any location that is too far from the new route.

The new route must be a subsequence of the original route that starts at p₁ and ends at p_n. Formally, the new route is p_i1 → p_i2 → … → p_im where 1 = i₁ < i₂ < … < i_m = n.

The assistants cannot skip a location p_j (where i_k < j < i_k+1) if its Euclidean distance to the straight-line segment connecting p_ik and p_ik+1 exceeds a given tolerance d. The distance from a point to a segment is computed as follows: for a point \(P=(x,y)\) and segment \(AB\) with \(A=(x_1,y_1)\) and \(B=(x_2,y_2)\), let the parameter

[ t = \frac{(P-A)\cdot(B-A)}{|B-A|^2} ]

If (0\le t\le 1), the distance is (|P - (A + t(B-A))|); otherwise it is (\min(|P-A|, |P-B|)). All calculations and comparisons with d should be done using this definition.

Your task is to help the assistants find a new route that minimizes the number of locations (i.e. the number of stops where the king gives a speech) while ensuring that for every segment of the new route and every skipped location between the endpoints of that segment, the distance requirement is satisfied.

Input/Output Details: See the following sections.

inputFormat

The first line contains two numbers: an integer n (\(2 \le n \le 10^5\), for example) and a floating-point number d representing the maximum allowed deviation.

The following n lines each contain two floating-point numbers representing the coordinates of the locations: x and y.

outputFormat

On the first line, output a single integer m representing the minimum number of locations in the new route.

On the second line, output m space-separated integers, indicating the indices (1-indexed) of the chosen locations in order.

sample

2 1
0 0
1 0

2
1 2