Kaukaisessa tulevaisuudessa ihmiskunta on löytänyt suuren, lämpimän ja rehevän planeetan asutettavaksi ja rakentaa paljon voimalaitoksia uuden siirtokunnan tueksi. Hämmästyttävä teknologia mahdollistaa maailmankaikkeuden valtavan energian valjastamisen. Rakentajat ovat kuitenkin jättäneet huomiotta pienen seikan: kahden voimalaitoksen rakentaminen liian lähelle toisiaan aiheuttaa huomattavan ketjureaktion riskin, mikä puolestaan johtaisi valtavaan räjähdykseen. Tätä tulee tietysti välttää.

Onneksi voimalaitoksissa voidaan käyttää kahdenlaista energiaa, joita kutsutaan valoenergiaksi ja pimeäksi energiaksi ja jotka eivät vuorovaikuta keskenään. Jos osa voimalaitoksista toimii valoenergialla ja osa pimeällä energialla, samanlaisten laitosten välinen etäisyys voi olla aiempaa suurempi, mikä tekisi koko hankkeesta vähemmän vaarallisen.

Tehtävä

Annettuna $n$ voimalaitoksen sijainnit (planeetta on tarpeeksi suuri, jotta voimme käsitellä niitä tason pisteinä), määrää jokaiselle laitokselle joko valoenergia tai pimeä energia siten, että kahden samanlaisen laitoksen välinen euklidinen etäisyys on mahdollisimman suuri. Reaalilukujen tulostamisen välttämiseksi tulosta vastauksena tämän suurimman etäisyyden neliö sekä voimalaitosten jako ”valo-” ja ”pimeisiin” laitoksiin.

Syöte

Syötteen ensimmäisellä rivillä on yksi kokonaisluku $N$ ($3 \le N \le 100\,000$) – voimalaitosten lukumäärä. Seuraavista $N$ rivistä $i$:nnellä on kaksi kokonaislukua $x_i, y_i$ ($0 \le x_i, y_i \le 10^9$) – $i$:nnen voimalaitoksen koordinaatit. Kaikki pisteet ovat erillisiä.

Tuloste

Tulosta tulosteen ensimmäiselle riville yksi kokonaisluku – suurimman saavutettavissa olevan etäisyyden neliö. Toisella rivillä tulee olla valoenergialla toimivien laitosten lukumäärä ja kolmannella rivillä välilyönnein eroteltu luettelo näiden laitosten numeroista. Neljännen ja viidennen rivin tulee kuvata pimeän energian laitokset samassa muodossa. Jos kelvollisia ratkaisuja on useita, tulosta mikä tahansa niistä.

Osatehtävät

Examples

Input 1

4
0 3
0 0
3 0
3 3

Output 1

18
2
1 3
2
2 4