#P18000. Triangles

Triangles

Triangles

题目描述

平面上有 nn 个整点,nn 能被 33 整除。这些点的横坐标构成 1,2,…,n1,2,\ldots,n 的一个排列,纵坐标也构成 1,2,…,n1,2,\ldots,n 的一个排列。

请将所有点划分成 n/3n/3 组,每组三个点作为一个三角形的顶点。每个点必须恰好使用一次。三角形可以退化,可以互相相交。

三角形的大小定义为其轴对齐最小包围矩形的周长,即包含它且四边分别平行于坐标轴的最小矩形的周长。一个划分的得分为所有三角形大小之和。

求最大可能得分,并输出一种达到最大值的划分。

输入格式

第一行一个整数 nn,满足 3≤n≤999993\le n\le99999 且 3∣n3\mid n。

接下来 nn 行,每行两个整数 x,yx,y,表示一个点。点按照输入顺序从 11 到 nn 编号。保证横坐标和纵坐标分别是 11 到 nn 的排列。

输出格式

第一行输出最大得分。

接下来 n/3n/3 行,每行三个点的编号,表示一个三角形。三角形的输出顺序、同一三角形三个点的顺序均任意。

样例 1

输入

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

输出

32
2 3 5
6 1 4