問題文

平面上の $n$ 個の格子点を考えます。ここで $n$ は $3$ で割り切れます。$x$ 座標は $1$ から $n$ までの整数の順列であり、$y$ 座標もまた $1$ から $n$ までの整数の順列です。

与えられた点を頂点とする $n/3$ 個の三角形からなる配置を 1 つ構成してください。各点は、いずれか 1 つの三角形の頂点として現れなければなりません。三角形は退化していてもよく、また自由に交差しても構いません。

配置のスコアは、そこに含まれるすべての三角形の大きさの総和です。三角形の大きさとは、その外接長方形（バウンディングボックス）の周長です。外接長方形とは、座標軸に平行な辺を持ち、その三角形を含む最小の長方形のことです。

達成可能な最大スコアを与える配置を 1 つ求めてください。

入力

1 行目には整数 $n$ ($3 \le n \le 99\,999$; $n$ は $3$ の倍数) が与えられます。

続く $n$ 行のそれぞれには 2 つの整数 $x$ と $y$ が与えられ、点の 1 つの座標を表します。$1$ から $n$ までの各整数は、$x$ 座標の中に 1 回ずつ、$y$ 座標の中にも 1 回ずつ現れます。

出力

1 行目に、達成可能な最大スコアを出力してください。

次に、このスコアを達成する任意の配置を出力してください。そのために、各行に 3 つの整数を含む $n/3$ 行を出力してください。これらは 1 つの三角形の頂点となる入力の点の番号を表します。点には入力順に $1$ から $n$ までの番号が付けられています。三角形およびその頂点は任意の順序で出力して構いません。

入出力例

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

32
2 3 5
6 1 4

注記