AlgoLiga 2018

Jeremy Clarkson, po zwolnieniu go z BBC, postanowił znaleźć w końcu porządną pracę. Pożyczył od Jamesa Maya Ferrari 458 Italia i został dostawcą pizzy. Jeremy musi dostarczyć jedzenie do n klientów, oczywiście zamierza to zrobić w swoim stylu. Nasz bohater postanowił rozpędzić się, a następnie wykonać poślizg nadsterowny pomiędzy domami klientów, cały czas skręcając w lewą stronę. Jeremy będzie wyrzucał pizze przez okno auta i nie pobierał za nie zapłaty. Plan jest genialny, pozostało jedynie wyznaczenie odpowiedniej trasy.

Twoim zadaniem jest połączenie n domów klientów odcinkami, w taki sposób, aby każda para sąsiadujących odcinków tworzyła skręt w lewo. Jednocześnie odcinki łączące domy nie mogą się przecinać.

Wejście

W pierwszej linii wejścia znajduje się jedna liczba całkowita n ∈ [1;100] oznaczająca liczbę klientów, do których Clarkson musi dostarczyć pizzę. W kolejnych n liniach znajdują się po dwie liczby całkowite x ∈ [-1000;1000] oraz y ∈ [-1000;1000] oznaczające współrzędne domów klientów. Gwarantujemy, że żadne 3 punkty nie będą współliniowe. Klienci numerowani są od 1 zgodnie z kolejnością na wejściu.

Wyjście

Na wyjściu należy wypisać n numerów klientów, w kolejności w jakiej Jeremy powinien ich odwiedzać, tak aby spełnione zostały założenia opisane w treści zadania. Jeżeli istnieje wiele poprawnych rozwiązań wypisz dowolne z nich.

Przykład

Wejście

6
4 3
-2 2
3 2
-1 -1
1 -2
-3 -3

Wyjście

3 1 2 6 5 4