I en avlägsen framtid har mänskligheten hittat en stor, varm och frodig planet att kolonisera, och bygger nu mängder av kraftverk för att försörja den nya kolonin. Den häpnadsväckande teknologin gör det möjligt för byggarna att utvinna Universums enorma energi. Det finns dock en liten detalj de har förbisett: att bygga två kraftverk för nära varandra medför en betydande risk för en kedjereaktion, vilket i sin tur skulle leda till en spektakulär explosion. Detta bör naturligtvis undvikas.

Lyckligtvis finns det två typer av energi som kan användas i kraftverken, kallade ljus och mörk energi, vilka inte växelverkar med varandra. Om några av kraftverken drivs med ljus energi och andra med mörk energi kan avståndet mellan likadana kraftverk bli större än tidigare, vilket skulle göra hela projektet mindre riskfyllt.

Uppgift

Givet positionerna för $n$ kraftverk (planeten är tillräckligt stor för att vi ska kunna betrakta dem som punkter i ett plan), tilldela varje kraftverk antingen ljus eller mörk energi så att det euklidiska avståndet mellan två kraftverk av samma typ blir så stort som möjligt. För att undvika utskrift av flyttal ska du som svar skriva ut kvadraten på detta maximala avstånd, samt uppdelningen av kraftverken i ”ljusa” och ”mörka”.

Indata

På den första raden i indata finns ett enda heltal $N$ ($3 \le N \le 100\,000$) – antalet kraftverk. Av de följande $N$ raderna innehåller den $i$-te raden två heltal $x_i, y_i$ ($0 \le x_i, y_i \le 10^9$) – koordinaterna för det $i$-te kraftverket. Alla punkter är olika.

Utdata

Skriv på den första raden i utdata ut ett enda heltal – kvadraten på det maximala avstånd som kan uppnås. Den andra raden ska innehålla antalet kraftverk som drivs med ljus energi, och den tredje raden en blankstegsseparerad lista med dessa kraftverks nummer. Den fjärde och femte raden ska beskriva kraftverken med mörk energi i samma format. Om det finns flera giltiga lösningar kan du skriva ut vilken som helst av dem.

Deluppgifter

Examples

Input 1

4
0 3
0 0
3 0
3 3

Output 1

18
2
1 3
2
2 4