Í fjarlægri framtíð fann mannkynið stóra, hlýja og gróskumikla plánetu til að nema og byggir nú fjölda orkuvera til að knýja nýju nýlenduna. Hin stórkostlega tækni gerir byggingaraðilum kleift að virkja hina gríðarlegu orku alheimsins. Þó er eitt lítið atriði sem þeim yfirsást: ef tvö orkuver eru byggð of nálægt hvort öðru skapast töluverð hætta á keðjuverkun, sem myndi aftur leiða til mikillar sprengingar. Þetta ber auðvitað að forðast.

Sem betur fer eru til tvær tegundir af orku sem hægt er að nota í orkuverum, kallaðar ljósorka og myrkurorka, sem víxlverka ekki hvor við aðra. Ef sum orkuveranna ganga fyrir ljósorku og önnur fyrir myrkurorku getur fjarlægðin milli eins orkuvera orðið meiri en áður, sem myndi gera alla framkvæmdina hættuminni.

Verkefni

Gefnar eru staðsetningar $n$ orkuvera (plánetan er nógu stór til að við getum litið á þau sem punkta í sléttu). Úthlutið hverju orkuveri annaðhvort ljósorku eða myrkurorku þannig að evklíðsk fjarlægð milli tveggja orkuvera af sömu gerð verði eins mikil og mögulegt er. Til að komast hjá því að prenta út rauntölur skal prenta sem svar ferning þessarar hámarksfjarlægðar, ásamt skiptingu orkuveranna í „ljós“ og „myrk“.

Inntak

Í fyrstu línu inntaksins er ein heiltala $N$ ($3 \le N \le 100\,000$) – fjöldi orkuvera. Af næstu $N$ línum inniheldur $i$-ta línan tvær heiltölur $x_i, y_i$ ($0 \le x_i, y_i \le 10^9$) – hnit $i$-ta orkuversins. Allir punktarnir eru ólíkir.

Úttak

Í fyrstu línu úttaksins skal prenta eina heiltölu – ferning hámarksfjarlægðarinnar sem hægt er að ná. Önnur línan á að innihalda fjölda orkuvera sem ganga fyrir ljósorku, og þriðja línan lista af númerum þessara orkuvera aðskildum með bilum. Fjórða og fimmta línan eiga að lýsa myrkurorkuverunum á sama sniði. Ef fleiri en ein gild lausn er til má prenta hverja sem er þeirra.

Undirverkefni

Examples

Input 1

4
0 3
0 0
3 0
3 3

Output 1

18
2
1 3
2
2 4