Недавно в город приехал известный цирк. Всего в этом цирке $$$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$$$ — номера акробатов в том порядке, в котором их стоит расположить в ряду.
3 10 70 30 40 50 60
2 3 1
4 99 99 11 11 88 88 55 55
2 4 3 1