Descrizione

Si considerino $n$ punti a coordinate intere su un piano, dove $n$ è divisibile per $3$. Le coordinate $x$ sono una permutazione degli interi da $1$ a $n$. Anche le coordinate $y$ sono una permutazione degli interi da $1$ a $n$.

Costruisci una configurazione di $n/3$ triangoli aventi per vertici i punti dati: ogni punto deve apparire come vertice di uno dei triangoli. I triangoli possono essere degeneri e possono intersecarsi liberamente.

Il punteggio di una configurazione è la somma delle dimensioni di tutti i triangoli in essa contenuti. La dimensione di un triangolo è il perimetro del suo rettangolo di delimitazione (bounding rectangle). Il rettangolo di delimitazione è il minimo rettangolo con i lati paralleli agli assi coordinati che contiene il triangolo.

Trova una configurazione che ottenga il massimo punteggio possibile.

Input

La prima riga contiene un intero $n$ ($3 \le n \le 99\,999$; $n$ è divisibile per $3$).

Ciascuna delle successive $n$ righe contiene due interi $x$ e $y$: le coordinate di uno dei punti. Ogni intero da $1$ a $n$ appare una volta tra le coordinate $x$ e una volta tra le coordinate $y$.

Output

Sulla prima riga, stampa il massimo punteggio possibile.

Successivamente, stampa una qualsiasi configurazione che ottenga questo punteggio. A tal fine, stampa $n/3$ righe con tre interi ciascuna: gli indici dei punti nell'input che sono i vertici di un triangolo. I punti sono numerati da $1$ a $n$ nell'ordine di input. I triangoli e i loro vertici possono essere stampati in qualsiasi ordine.

Esempio

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

32
2 3 5
6 1 4

Note