W odległej przyszłości ludzkość odnalazła dużą, ciepłą i bujną planetę do skolonizowania i buduje wiele elektrowni, aby utrzymać nową kolonię. Zdumiewająca technologia pozwala budowniczym ujarzmić ogromną energię Wszechświata. Jest jednak pewien drobny szczegół, który przeoczyli: zbudowanie dwóch elektrowni zbyt blisko siebie niesie ze sobą znaczne ryzyko reakcji łańcuchowej, która z kolei doprowadziłaby do spektakularnej eksplozji. Tego oczywiście należy uniknąć.

Na szczęście istnieją dwa rodzaje energii, których można używać w elektrowniach, zwane jasną i ciemną energią, które nie oddziałują ze sobą. Jeśli część elektrowni będzie działać na jasnej energii, a część na ciemnej, odległość między jednakowymi elektrowniami może być większa niż wcześniej, co uczyni całe przedsięwzięcie mniej niebezpiecznym.

Zadanie

Mając dane położenia $n$ elektrowni (planeta jest wystarczająco duża, abyśmy mogli traktować je jako punkty na płaszczyźnie), przypisz każdej elektrowni jasną albo ciemną energię tak, aby odległość euklidesowa między dwiema elektrowniami tego samego typu była możliwie największa. Aby uniknąć wypisywania liczb rzeczywistych, wypisz jako odpowiedź kwadrat tej maksymalnej odległości, a także podział elektrowni na „jasne” i „ciemne”.

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba całkowita $N$ ($3 \le N \le 100\,000$) – liczba elektrowni. Spośród kolejnych $N$ wierszy $i$-ty zawiera dwie liczby całkowite $x_i, y_i$ ($0 \le x_i, y_i \le 10^9$) – współrzędne $i$-tej elektrowni. Wszystkie punkty są parami różne.

Wyjście

W pierwszym wierszu wyjścia wypisz jedną liczbę całkowitą – kwadrat maksymalnej odległości, jaką można osiągnąć. Drugi wiersz powinien zawierać liczbę elektrowni działających na jasnej energii, a trzeci wiersz – oddzieloną spacjami listę numerów tych elektrowni. Czwarty i piąty wiersz powinny opisywać elektrownie na ciemnej energii w tym samym formacie. Jeśli istnieje wiele poprawnych rozwiązań, wypisz dowolne z nich.

Podzadania

Przykład

Wejście 1

4
0 3
0 0
3 0
3 3

Wyjście 1

18
2
1 3
2
2 4