遠い未来、人類は入植のために巨大で温暖かつ緑豊かな惑星を発見し、新しい植民地を支えるために多くの発電所を建設している。驚異的な技術により、建設者たちは宇宙の莫大なエネルギーを利用することができる。しかし、彼らが見落としていた小さな事実がある。2 つの発電所を互いに近づけて建設しすぎると、連鎖反応を引き起こすかなりの危険が生じ、結果として大爆発につながってしまうのである。これは当然避けなければならない。

幸いなことに、発電所で使用できるエネルギーには光エネルギーと闇エネルギーと呼ばれる 2 種類があり、これらは互いに相互作用しない。いくつかの発電所が光エネルギーで稼働し、いくつかが闇エネルギーで稼働すれば、同じ種類の発電所間の距離を以前より大きくできる可能性があり、事業全体の危険性を減らすことができる。

課題

$n$ 個の発電所の位置（惑星は十分に大きいため、平面上の点として扱うことができる）が与えられたとき、同じ種類の 2 つの発電所間のユークリッド距離が可能な限り最大になるように、各発電所に光エネルギーまたは闇エネルギーのいずれかを割り当てよ。実数の出力を避けるため、答えとしてこの最大距離の 2 乗と、発電所の「光」と「闇」への分割を出力せよ。

入力

入力の 1 行目には、発電所の個数を表す 1 つの整数 $N$（$3 \le N \le 100\,000$）が与えられる。続く $N$ 行のうち $i$ 行目には、$i$ 番目の発電所の座標を表す 2 つの整数 $x_i, y_i$（$0 \le x_i, y_i \le 10^9$）が与えられる。すべての点は互いに異なる。

出力

出力の 1 行目に、達成可能な最大距離の 2 乗を表す 1 つの整数を出力せよ。2 行目には光エネルギーで稼働する発電所の個数を、3 行目にはそれらの発電所の番号を空白区切りで並べたリストを出力せよ。4 行目と 5 行目には、同じ形式で闇エネルギーの発電所について記述せよ。有効な解が複数存在する場合は、そのうちのどれを出力してもよい。

小課題

入出力例

入力 1

4
0 3
0 0
3 0
3 3

出力 1

18
2
1 3
2
2 4