Недавно в город приехал известный цирк. Всего в этом цирке \(n\) акробатов, и в этот раз в честь проведения СПбКОШП 2022 они подготовили особенный номер.
Известно, что \(i\)-й акробат имеет рост \(a_i\) и вес \(b_i\). Любые три акробата могут собраться вместе и показать необычный трюк. Если трюк показывают акробаты с номерами \(i\), \(j\) и \(k\), то эффектность трюка оценивается как \(a_i b_j + a_j b_k + a_k b_i\).
Тренер акробатов считает упорядоченную тройку акробатов \((i, j, k)\) хорошей, если эффектность их трюка будет не меньше, чем если они расположатся в обратном порядке \((k, j, i)\).
Для номера тренер хочет расположить всех \(n\) акробатов в один ряд так, чтобы любая тройка подряд идущих акробатов была хорошей. Помогите ему с этой нелегкой задачей!
Формат входных данных
В первой строке ввода дано целое число \(n\) — количество акробатов в цирке (\(3 \leqslant n \leqslant 1000\)).
В \(i\)-й из следующих \(n\) строк через пробел даны целые числа \(a_i\) и \(b_i\) — рост и вес \(i\)-го акробата (\(1 \leqslant a_i, b_i \leqslant 10^9\)).
Формат входных данных
Выведите через пробел \(n\) различных целых чисел от \(1\) до \(n\) — номера акробатов в том порядке, в котором их стоит расположить в ряду.
Примеры
| № | Входные данные | Выходные данные |
|
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
|