Christmas Tree Lighting

In the year 3202 Christmas is around the corner. Little Ω has bought a Christmas tree along with a long wire festooned with colored lights. The tree is modeled as a convex polygon with n vertices on the plane. These vertices are given in counterclockwise order and numbered 1, 2, …, n. Let the vertex with the maximum y–coordinate be k (if there are several, choose the one with the smallest index).

To decorate the tree, Little Ω wishes to fix the wire to the polygon at all vertices – each vertex must be visited exactly once. Moreover, to plug in the wire the journey must start at vertex k. Formally, you are to choose a permutation p₁, p₂, …, p_n of the vertices satisfying p₁ = k so that the total wire length

\(\sum_{i=1}^{n-1} d((x_{p_i},y_{p_i}),(x_{p_{i+1}},y_{p_{i+1}}))\)

is minimized (where \(d((x,y),(x',y')) = \sqrt{(x-x')^2+(y-y')^2}\) is the Euclidean distance). Due to precision issues, a solution is accepted if its total length has an absolute or relative error of at most \(10^{-10}\) compared to the optimum.

Hint: Since the vertices form a convex polygon, the optimal Hamiltonian path (without the need to return to the starting vertex) can be obtained by first identifying the vertex with the minimum y–coordinate (say t). These two extreme vertices, k and t, split the boundary into two chains: one obtained by going clockwise from k to t and the other by going counterclockwise. Interleaving these two chains optimally (using dynamic programming) yields a path with minimal total distance. Your task is to output one such ordering that starts at k and (necessarily) ends at t.

inputFormat

The first line contains an integer n (at least 3).

Each of the next n lines contains two real numbers x_i and y_i – the coordinates of vertex i.

outputFormat

Output a permutation of the numbers 1, 2, …, n (separated by spaces) representing the order in which the wire visits the vertices. The first vertex must be the one with maximum y–coordinate. The ordering must achieve a total wire length that is optimal up to an absolute or relative error of \(10^{-10}\).

sample

4
0 0
1 0
1 1
0 1

3 4 2 1