Ti vengono dati $N$ punti distinti sul piano 2D, numerati da $1$ a $N$. Le coordinate del punto $i$ sono $(x_i, y_i)$.
Ogni punto ha un colore. Ci sono $N$ colori in totale, numerati da $1$ a $N$, e il punto $i$ ha il colore $c_i$.
Il tuo compito è selezionare quattro punti con colori a due a due distinti, collegarli in qualsiasi ordine e formare un quadrilatero. Il quadrilatero può avere un angolo interno esattamente di $180^\circ$, ma nessuna coppia di lati non adiacenti può intersecarsi.
Determina se un tale quadrilatero può essere formato. Se è possibile, sia $S$ l'area massima possibile tra tutti i quadrilateri validi, e stampa $2S$ come intero. Se non può essere formato, stampa $0$.
Ci sono $T$ casi di test indipendenti.
Input
L'input è fornito nel seguente formato:
T case1 case2 : caseT
Qui, ciascun $\text{case}_i$ è dato nella seguente forma:
N x1 y1 c1 x2 y2 c2 : xN yN cN
- Tutti i valori di input sono interi.
- $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$
- Se $i \neq j$, allora $(x_i, y_i) \neq (x_j, y_j)$.
- La somma totale di $N$ su tutti i casi di test non supera $10^5$.
Output
Per ciascun caso di test, stampa la risposta su una riga separata.
Esempi
Input di esempio 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
Output di esempio 1
15 17 0 20000000000000000
Note
Nel primo esempio, collegando i punti $1, 2, 3, 6$ in questo ordine si forma un quadrilatero valido di area $15/2$, che è il massimo tra tutte le scelte valide. Il quadrilatero formato dai punti $1, 2, 4, 5$ ha area $9$, ma i punti $1$ e $4$ hanno lo stesso colore, quindi non è valido.
Nel secondo esempio esiste un quadrilatero valido, ma nessun quadrilatero convesso soddisfa i requisiti.
Nel terzo esempio non è possibile formare alcun quadrilatero valido.
Come mostrato nel quarto esempio, la risposta può essere molto grande.