410337: GYM104010 I Circus Performance

A very famous circus is in the city! There are exactly $$$n$$$ acrobats in the circus, and this time they prepared a special show in honor of the SPb Team School Programming Olympiad 2022.

It is known that the $$$i$$$-th acrobat has a height equal to $$$a_i$$$ and weight equal to $$$b_i$$$. Any three acrobats can get together and perform an unusual stunt. If acrobats with numbers $$$i$$$, $$$j$$$ and $$$k$$$ perform a stunt, the efficiency of the stunt is estimated as $$$a_i b_j + a_j b_k + a_k b_i$$$.

A circus' trainer considers an ordered trio of acrobats $$$(i, j, k)$$$ good if the efficiency of their stunt is no less than if they are arranged in reverse order $$$(k, j, i)$$$.

For the final act of the show the trainer wants line up all $$$n$$$ acrobats so that any triple of consecutive acrobats would be good. Help him with this difficult task!

The first line of input contains an integer $$$n$$$ representing the number of acrobats in the circus ($$$3 \leq n \leq 1000$$$).

In the $$$i$$$-th of the following $$$n$$$ lines there are two space-separated integers $$$a_i$$$ and $$$b_i$$$ — the height and weight of the $$$i$$$-th acrobat ($$$1 \leq a_i, b_i \leq 10^9$$$).

Print $$$n$$$ different integers from $$$1$$$ to $$$n$$$ — the numbers of acrobats in the order in which they should be lined up.

3
10 70
30 40
50 60

2 3 1 

4
99 99
11 11
88 88
55 55

2 4 3 1