Boat
A Viking ship is navigating the vast ocean in search of Valhalla. Unfortunately, the rudder is lost, and half of the oars are missing, so the ship can only turn using water eddies, of which there are n on the map. However, the ship can only travel north, south, west, or east both before and after a turn. The journey begins at the first eddy and concludes at the last one. How much strength will remain for the final battle? Outsmart the cunning Loki by proposing the best route for the ship. The gods will favor a route that requires the fewest turns, and among such routes, the shortest one. Note that at the start of the journey, the ship is facing north.
Input
The first line of the input file contains a single integer n. The following n lines each contain two integers, representing the coordinates of each eddy. All eddies are located at distinct points. 2 ≤ n ≤ 100000, and all coordinates do not exceed 10^9 in absolute value. North corresponds to an increase in the y coordinate.
Output
Output two lines. The first line should contain two integers: the minimum number of turns required and the minimum distance. The second line should describe the optimal path: the sequence of eddy numbers in the order they are visited, starting with the first and ending with the last, without any repetitions.
If the ship cannot find a path, output a single line with two numbers -1.