Beschreibung

Betrachte $n$ ganzzahlige Punkte in einer Ebene, wobei $n$ durch $3$ teilbar ist. Die $x$-Koordinaten bilden eine Permutation der ganzen Zahlen von $1$ bis $n$. Die $y$-Koordinaten bilden ebenfalls eine Permutation der ganzen Zahlen von $1$ bis $n$.

Konstruiere eine Konfiguration aus $n/3$ Dreiecken mit Eckpunkten in den gegebenen Punkten: Jeder Punkt muss als Eckpunkt eines der Dreiecke vorkommen. Die Dreiecke dürfen entartet sein und sich beliebig schneiden.

Die Punktzahl einer Konfiguration ist die Summe der Größen aller darin enthaltenen Dreiecke. Die Größe eines Dreiecks ist der Umfang seines umschließenden Rechtecks (Bounding Rectangle). Das umschließende Rechteck ist das kleinste Rechteck mit achsenparallelen Seiten, welches das Dreieck enthält.

Finde eine Konfiguration, welche die maximal mögliche Punktzahl erreicht.

Eingabe

Die erste Zeile enthält eine ganze Zahl $n$ ($3 \le n \le 99\,999$; $n$ ist durch $3$ teilbar).

Jede der nächsten $n$ Zeilen enthält zwei ganze Zahlen $x$ und $y$: die Koordinaten eines der Punkte. Jede ganze Zahl von $1$ bis $n$ kommt genau einmal unter den $x$-Koordinaten und genau einmal unter den $y$-Koordinaten vor.

Ausgabe

Gib in der ersten Zeile die maximal mögliche Punktzahl aus.

Gib anschließend eine beliebige Konfiguration aus, die diese Punktzahl erreicht. Gib dazu $n/3$ Zeilen mit jeweils drei ganzen Zahlen aus: die Nummern der Punkte aus der Eingabe, welche die Eckpunkte eines Dreiecks bilden. Die Punkte sind in der Eingabereihenfolge von $1$ bis $n$ nummeriert. Die Dreiecke und ihre Eckpunkte können in beliebiger Reihenfolge ausgegeben werden.

Beispiel

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

32
2 3 5
6 1 4

Hinweis