Du får $N$ skilda punkter i 2D-planet, numrerade $1$ till $N$. Koordinaterna för punkt $i$ är $(x_i, y_i)$.
Varje punkt har en färg. Det finns totalt $N$ färger, numrerade $1$ till $N$, och punkt $i$ har färgen $c_i$.
Din uppgift är att välja fyra punkter med parvis skilda färger, förbinda dem i valfri ordning och bilda en fyrhörning. Fyrhörningen får ha en innervinkel på exakt $180^\circ$, men inget par av icke-intilliggande kanter får skära varandra.
Avgör om en sådan fyrhörning kan bildas. Om det går, låt $S$ vara den maximalt möjliga arean över alla giltiga fyrhörningar, och skriv ut $2S$ som ett heltal. Om det inte går, skriv ut $0$.
Det finns $T$ oberoende testfall.
Indata
Indatan ges i följande format:
T case1 case2 : caseT
Här ges varje $\text{case}_i$ på följande form:
N x1 y1 c1 x2 y2 c2 : xN yN cN
- Alla indatavärden är heltal.
- $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$
- Om $i \neq j$, så är $(x_i, y_i) \neq (x_j, y_j)$.
- Den totala summan av $N$ över alla testfall överstiger inte $10^5$.
Utdata
För varje testfall, skriv ut svaret på en egen rad.
Exempel
Exempelindata 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
Exempelutdata 1
15 17 0 20000000000000000
Förklaring
I det första exemplet bildar punkterna $1, 2, 3, 6$ förbundna i denna ordning en giltig fyrhörning med area $15/2$, vilket är det maximala bland alla giltiga val. Fyrhörningen som bildas av punkterna $1, 2, 4, 5$ har area $9$, men punkterna $1$ och $4$ har samma färg, så den är ogiltig.
I det andra exemplet finns en giltig fyrhörning, men ingen konvex fyrhörning uppfyller kraven.
I det tredje exemplet kan ingen giltig fyrhörning bildas.
Som visas i det fjärde exemplet kan svaret bli mycket stort.