Circus Performance

시간 제한1초메모리 제한1024 MB

요약

모든 n명의 곡예사를 일렬로 세울 때 연속한 세 명 (i,j,k)마다 a_i*b_j + a_j*b_k + a_k*b_i >= a_k*b_j + a_j*b_i + a_i*b_k를 만족하도록 순서를 정한다.

난이도: 보통10점 중 7점
유형: 수학, 그리디, 정렬
정답자: 아직 제출이 없습니다

문제

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.

예제2

예제 1
입력
```
3
10 70
30 40
50 60
```
예상 출력
```
2 3 1
```
예제 2
입력
```
4
99 99
11 11
88 88
55 55
```
예상 출력
```
2 4 3 1
```