Achtung!

Time limit2sMemory limit1024 MB

Summary

Order n distinct points into a closed route whose straight segments never cross or touch except at shared endpoints, or report that no such route exists.

Level: Medium6 of 10
Topics: Geometry, Sorting, Implementation
Solved: No attempts yet

Problem

Achtung! The mechanical nanny has been switched on, and now it chases Pin, trying to surround him with affection and care! Pin's yard has $n$ bunkers. He would love to hide in one of them, but each bunker has a very important and very urgent task waiting.

So Pin asks you to plan a route between the bunkers that visits each one exactly once and returns to the starting bunker. Pin may begin at any bunker.

Pin wrote the interception program for the nanny himself and assembled its engine, so he knows for certain he will be caught if he runs from one bunker to another along a path that is not a straight line, or if he runs through the same place twice. Crossing or touching a segment he has already run also counts as running through it twice.

Input

The input file describes Pin's yard.

The first line contains one integer $n$ ( $1 \le n \le 100{,}000$ ), the number of bunkers. Each of the next $n$ lines contains two integers $x_i$ and $y_i$ ( $|x_i|, |y_i| \le 10^9$ ), the coordinates of the entrance to the $i$ -th bunker. An entrance is so small compared to the yard that it is treated as a point. No two bunkers lie at the same point.

Output

The output file contains a permutation of $n$ numbers, the bunker numbers in the order Pin visits them. If no route exists along which Pin can run without being caught by the nanny, output 'No solution'.

Examples2

Example 1
Input
```
4
0 0
0 1
1 0
1 1
```
Expected output
```
1 2 4 3
```
Example 2
Input
```
3
0 0
0 1
0 2
```
Expected output
```
No solution
```