I en fjern fremtid har menneskeheten funnet en stor, varm og frodig planet å kolonisere, og bygger mange kraftverk for å forsyne den nye kolonien. Den forbløffende teknologien gjør det mulig for utbyggerne å utnytte Universets enorme energi. Det er imidlertid en liten detalj de har oversett: å bygge to kraftverk for nær hverandre gir en betydelig risiko for en kjedereaksjon, som igjen vil føre til en spektakulær eksplosjon. Dette bør åpenbart unngås.

Heldigvis finnes det to typer energi som kan brukes i kraftverkene, kalt lys og mørk energi, som ikke vekselvirker med hverandre. Hvis noen av kraftverkene drives med lys energi og noen med mørk energi, kan avstanden mellom like kraftverk bli større enn før, noe som vil gjøre hele foretaket mindre farlig.

Oppgave

Gitt posisjonene til $n$ kraftverk (planeten er stor nok til at vi kan betrakte dem som punkter i et plan), tildel hvert kraftverk enten lys eller mørk energi slik at den euklidske avstanden mellom to kraftverk av samme type blir størst mulig. For å unngå utskrift av reelle tall skal du som svar skrive ut kvadratet av denne maksimale avstanden, samt oppdelingen av kraftverkene i «lyse» og «mørke».

Inndata

På den første linjen i inndata står et enkelt heltall $N$ ($3 \le N \le 100\,000$) – antallet kraftverk. Av de følgende $N$ linjene inneholder den $i$-te linjen to heltall $x_i, y_i$ ($0 \le x_i, y_i \le 10^9$) – koordinatene til det $i$-te kraftverket. Alle punktene er forskjellige.

Utdata

På den første linjen i utdata skal du skrive ut et enkelt heltall – kvadratet av den maksimale avstanden som kan oppnås. Den andre linjen skal inneholde antallet kraftverk som drives med lys energi, og den tredje linjen en mellomromseparert liste over numrene til disse kraftverkene. Den fjerde og femte linjen skal beskrive kraftverkene med mørk energi på samme format. Hvis det finnes flere gyldige løsninger, kan du skrive ut hvilken som helst av dem.

Deloppgaver

Examples

Input 1

4
0 3
0 0
3 0
3 3

Output 1

18
2
1 3
2
2 4