Given n points on the plane p_{1} … p_{n}
no three of which are collinear,
find a permutation of the points p_{i1} … p_{in}
such that the n segments
(p_{i1}, p_{i2}), (p_{i2}, p_{i3}), …, (p_{in−1}, p_{in}), (p_{in}, p_{i1})
form a non-degenerate polygon,
that is, one that does not cross itself.

Input

Input consists of several cases,
each one with n followed by n points
with integer coordinates not larger than 10^{7} in absolute value.
Assume 3 ≤ n ≤ 10^{4},
and that no three given points are collinear.

Output

For every case, print a correct polygon constructed from the n points. If there is more than one solution, print any of them. If there is no solution, print “Ivan is a troll”.

Public test cases

**Input**

4 0 0 1 1 0 1 1 0 3 0 0 10 10 15 20 5 -1 -1 -3 -3 -1 1 1 -2 -2 0 4 0 0 -1 1 0 -1 1 -2 7 -9 -4 0 -5 2 3 1 7 0 0 5 -5 1 4

**Output**

1 4 2 3 1 2 3 2 4 1 3 5 3 4 1 2 1 2 6 5 3 7 4

Information

- Author
- Ivan Geffner
- Language
- English
- Official solutions
- C++
- User solutions
- C++