Beskrivelse

Betrakt $n$ heltallspunkter i et plan, der $n$ er delelig med $3$. Koordinatene $x$ er en permutasjon av heltallene fra $1$ til $n$. Koordinatene $y$ er også en permutasjon av heltallene fra $1$ til $n$.

Konstruer en konfigurasjon av $n/3$ trekanter med hjørner i de gitte punktene: hvert punkt må forekomme som et hjørne i én av trekantene. Trekantene kan være degenererte og kan krysse hverandre fritt.

Poengsummen til en konfigurasjon er summen av størrelsene til alle trekantene i den. Størrelsen til en trekant er omkretsen til dens omsluttende rektangel (bounding rectangle). Det omsluttende rektangelet er det minimale rektangelet med sider parallelle med koordinataksene som inneholder trekanten.

Finn en konfigurasjon som oppnår den maksimalt mulige poengsummen.

Inndata

Den første linjen inneholder et heltall $n$ ($3 \le n \le 99\,999$; $n$ er delelig med $3$).

Hver av de neste $n$ linjene inneholder to heltall $x$ og $y$: koordinatene til ett av punktene. Hvert heltall fra $1$ til $n$ forekommer én gang blant $x$-koordinatene og én gang blant $y$-koordinatene.

Utdata

På den første linjen skal du skrive ut den maksimalt mulige poengsummen.

Deretter skal du skrive ut en hvilken som helst konfigurasjon som oppnår denne poengsummen. For å gjøre det, skriv ut $n/3$ linjer med tre heltall på hver: numrene på punktene i inndata som er hjørnene i en trekant. Punktene er nummerert fra $1$ til $n$ i inndatarekkefølgen. Trekantene og hjørnene deres kan skrives ut i hvilken som helst rekkefølge.

Eksempel

6
6 5
3 6
5 3
2 4
1 1
4 2

32
2 3 5
6 1 4

Merk