Problem C
Landsreisa

Stefán and Eva live in Vestmannaeyjar. Eva wants to see the entire country. They intend to visit every location in the country exactly once and then end up back in Vestmannaeyjar. Stefán hates traveling and thus wants to spend the least amount of time traveling between locations. If Stefán travels for too long he gets annoyed which in turn annoys Eva. Eva wants to keep Stefán in a good mood and thus has asked for your help making a travel plan. The shorter the travel plan the more satisfied Stefán will be.

The starting location of Stefán and Eva is location $0$. They always travel with the same speed between locations. It’s possible to travel between any two locations in both directions. To simplify things the world is two dimensional, where each longitude has been converted into an $x$ value and each latitude has been converted into a $y$ value. Since the world is two dimensional we use Euclidean distance.

Input

The input to this problem is not secret like in other problems, it can be found here.

The first line contains an integer $n$, the number of locations. Next there are $n$ lines. Each contains two real numbers $x$ and $y$ where $-25\le x\le -13$ and $63\le y\le 67$. The $i$-th line denotes the coordinates of location $i$. The values have at most $4$ digits after the decimal point. Below there is an image of the given input.

Output

Print the travel plan on one line with $n$ numbers, separated by spaces, where each number is between $0$ and $n-1$ with each value appearing exactly once. The numbers should signify in what order the locations are visited. The first value should always be $0$.

Scoring

The score is given as an integer $0\le x\le 100$. If the length of your travel plan is $k$ then $x=\lfloor 100\cdot {(1-\frac{k-63}{100})}^4\rfloor$.

Locations in Iceland