二次元平面上に $N$ 個の相異なる点が与えられ、$1$ から $N$ までの番号が付けられています。点 $i$ の座標は $(x_i, y_i)$ です。
各点には色が付いています。色は全部で $N$ 種類あり、$1$ から $N$ までの番号が付けられています。点 $i$ の色は $c_i$ です。
あなたの仕事は、色が互いに異なる四つの点を選び、それらを任意の順序で結んで四角形を作ることです。この四角形はちょうど $180^\circ$ の内角を持っても構いませんが、隣り合わない二辺が交差してはなりません。
このような四角形を作ることができるか判定してください。作ることができる場合、条件を満たす四角形の面積の最大値を $S$ として、$2S$ を整数として出力してください。作ることができない場合は $0$ を出力してください。
$T$ 個の独立なテストケースが与えられます。
入力
入力は以下の形式で与えられます:
T case1 case2 : caseT
ここで、各 $\text{case}_i$ は以下の形式で与えられます:
N x1 y1 c1 x2 y2 c2 : xN yN cN
- 入力される値はすべて整数である。
- $1 \le T \le 10^4$
- $4 \le N \le 10^5$
- $|x_i|, |y_i| \le 10^8$
- $1 \le c_i \le N$
- $i \neq j$ ならば $(x_i, y_i) \neq (x_j, y_j)$ である。
- すべてのテストケースにおける $N$ の総和は $10^5$ を超えない。
出力
各テストケースについて、答えをそれぞれ一行に出力してください。
入出力例
入力例 1
4 6 2 4 1 5 4 2 6 2 3 5 1 1 2 1 2 1 3 4 4 1 1 1 3 5 2 7 2 3 4 3 4 5 0 0 1 0 1 2 1 0 2 0 2 3 2 0 3 4 0 0 1 0 100000000 2 100000000 0 3 100000000 100000000 4
出力例 1
15 17 0 20000000000000000
ノート
最初の例では、点 $1, 2, 3, 6$ をこの順に結ぶと面積 $15/2$ の有効な四角形が得られ、これはすべての有効な選び方の中で最大です。点 $1, 2, 4, 5$ からなる四角形の面積は $9$ ですが、点 $1$ と点 $4$ の色が同じであるため無効です。
二番目の例では、有効な四角形は存在しますが、条件を満たす凸四角形は存在しません。
三番目の例では、有効な四角形を作ることはできません。
四番目の例に示されている通り、答えは非常に大きくなることがあります。