Description

Considérons $n$ points à coordonnées entières dans le plan, où $n$ est divisible par $3$. Les abscisses $x$ forment une permutation des entiers de $1$ à $n$. Les ordonnées $y$ forment également une permutation des entiers de $1$ à $n$.

Construisez une configuration de $n/3$ triangles ayant pour sommets les points donnés : chaque point doit apparaître comme sommet de l'un des triangles. Les triangles peuvent être dégénérés et peuvent s'intersecter librement.

Le score d'une configuration est la somme des tailles de tous les triangles qui la composent. La taille d'un triangle est le périmètre de son rectangle englobant. Le rectangle englobant est le plus petit rectangle à côtés parallèles aux axes de coordonnées qui contient le triangle.

Trouvez une configuration qui atteint le score maximal possible.

Entrée

La première ligne contient un entier $n$ ($3 \le n \le 99\,999$ ; $n$ est divisible par $3$).

Chacune des $n$ lignes suivantes contient deux entiers $x$ et $y$ : les coordonnées de l'un des points. Chaque entier de $1$ à $n$ apparaît une fois parmi les coordonnées $x$ et une fois parmi les coordonnées $y$.

Sortie

Sur la première ligne, affichez le score maximal possible.

Ensuite, affichez n'importe quelle configuration qui atteint ce score. Pour cela, affichez $n/3$ lignes contenant chacune trois entiers : les numéros des points de l'entrée qui forment les sommets d'un triangle. Les points sont numérotés de $1$ à $n$ dans l'ordre de l'entrée. Les triangles et leurs sommets peuvent être affichés dans n'importe quel ordre.

Exemple

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

32
2 3 5
6 1 4

Note