It is a classical Traveling Salesman Problem. The traveling salesman wants to visit *n* cities. For each city, he knows its coordinates (*x*, *y*). Traveling between cities with coordinates (*x<sub>1</sub>*, *y<sub>1</sub>*) and (*x<sub>2</sub>*, *y<sub>2</sub>*) takes him the amount of time proportional to their Euclidian distance defined as follows:

$$\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}$$

In the above equation *v* is the constant velocity of the salesman. In this problem we assume that it is equal to 1. 

Determine the route for a traveling salesman that minimizes the total time spent on the trip.

#### Input

The input consists of *n* lines, 1 <= *n* <= 2500 denoting the number of cities. Each of these lines contains one integer number 1 <= *id* <= 10000 and two float numbers 1 <= *x, y* <= 10<sup>5</sup>. These are identificators and coordinates of each city.

#### Output

The output should contain the permutation of all  *n* identificators presenting the order of cities that the salesman should use to visit them. After visiting the last city, **the salesman has to return to the first one**.

#### Scoring

For each test case, your program will receive the score equal to the time spent on the trip and in all cities. You should minimize this value. For each test, your program should execute below 1 second.

#### Example Input

```2 -100 -100
4 70 -90
6 100 200
```

#### Example output

Not necessarily the best output for the input presented above is following: 

```2 4 6
```

#### Remarks

[Traveling Salesman Problem](https://en.wikipedia.org/wiki/Travelling_salesman_problem) is a classical NP-hard problem in combinatorial optimization, defined in the 18th century. The implementation published at Optil.io uses some of the instances included in the TSPLIB - standard library of test instances for TSP [1].

[1] Reinelt, G. (1991). TSPLIB - A traveling salesman problem library. *ORSA Journal on Computing*, 3(4), 376-384.