Circus Performance

Time limit1sMemory limit1024 MB

Summary

Given n acrobats with heights and weights, output an order so every three consecutive acrobats have forward stunt efficiency at least the reverse efficiency.

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

Problem

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

The $i$ -th acrobat has height $a_i$ and weight $b_i$ . Any three acrobats can get together and perform an unusual stunt. If acrobats $i$ , $j$ , and $k$ perform a stunt, the efficiency of the stunt is $a_i b_j + a_j b_k + a_k b_i$ .

The trainer considers an ordered trio of acrobats $(i, j, k)$ good if the efficiency of their stunt is no less than the efficiency when they perform in reverse order $(k, j, i)$ .

For the final act, the trainer wants to line up all $n$ acrobats so that every triple of consecutive acrobats is good. Help him with this difficult task!

Input

The first line contains an integer $n$ , the number of acrobats ( $3 \leq n \leq 1000$ ).

Each of the following $n$ lines contains 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$ ).

Output

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

Examples2

Example 1
Input
```
3
10 70
30 40
50 60
```
Expected output
```
2 3 1
```
Example 2
Input
```
4
99 99
11 11
88 88
55 55
```
Expected output
```
2 4 3 1
```