Kuvaus

Tarkastellaan tason $n$:ää kokonaislukupistettä, missä $n$ on jaollinen $3$:lla. Pisteiden $x$-koordinaatit muodostavat lukujen $1$–$n$ permutaation. Myös $y$-koordinaatit muodostavat lukujen $1$–$n$ permutaation.

Muodosta $n/3$ kolmion asetelma, jossa kolmioiden kärjet ovat annetuissa pisteissä: jokaisen pisteen on esiinnyttävä jonkin kolmion kärkenä. Kolmiot voivat olla degeneroituneita ja ne voivat leikata toisiaan vapaasti.

Asetelman pistemäärä on kaikkien siihen kuuluvien kolmioiden kokojen summa. Kolmion koko on sitä ympäröivän suorakulmion (bounding rectangle) piiri. Ympäröivä suorakulmio on pienin suorakulmio, jonka sivut ovat koordinaattiakselien suuntaiset ja joka sisältää kyseisen kolmion.

Etsi asetelma, joka saavuttaa suurimman mahdollisen pistemäärän.

Syöte

Ensimmäinen rivi sisältää kokonaisluvun $n$ ($3 \le n \le 99\,999$; $n$ on jaollinen $3$:lla).

Jokainen seuraavista $n$ rivistä sisältää kaksi kokonaislukua $x$ ja $y$: yhden pisteen koordinaatit. Jokainen kokonaisluku väliltä $1$–$n$ esiintyy kerran $x$-koordinaattien joukossa ja kerran $y$-koordinaattien joukossa.

Tuloste

Tulosta ensimmäiselle riville suurin mahdollinen pistemäärä.

Tulosta seuraavaksi mikä tahansa asetelma, joka saavuttaa tämän pistemäärän. Tulosta sitä varten $n/3$ riviä, joista jokaisella on kolme kokonaislukua: syötteen pisteiden numerot, jotka muodostavat yhden kolmion kärjet. Pisteet on numeroitu $1$:stä $n$:ään syötejärjestyksessä. Kolmiot ja niiden kärjet voidaan tulostaa missä tahansa järjestyksessä.

Esimerkki

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

32
2 3 5
6 1 4

Huomautus