Du får gitt $N$ forskjellige punkter i 2D-planet, nummerert fra $1$ til $N$. Koordinatene til punkt $i$ er $(x_i, y_i)$.
Hvert punkt har en farge. Det er totalt $N$ farger, nummerert fra $1$ til $N$, og punkt $i$ har farge $c_i$.
Din oppgave er å velge fire punkter med parvis forskjellige farger, forbinde dem i en hvilken som helst rekkefølge og danne en firkant. Firkanten kan ha en indre vinkel på nøyaktig $180^\circ$, men ingen par av ikke-tilstøtende kanter kan krysse hverandre.
Avgjør om en slik firkant kan dannes. Hvis det er mulig, la $S$ være det maksimalt mulige arealet over alle gyldige firkanter, og skriv ut $2S$ som et heltall. Hvis den ikke kan dannes, skriv ut $0$.
Det er $T$ uavhengige testtilfeller.
Inndata
Inndataene er gitt på følgende format:
T case1 case2 : caseT
Her er hver $\text{case}_i$ gitt på følgende form:
N x1 y1 c1 x2 y2 c2 : xN yN cN
- Alle inndataverdier er heltall.
- $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$
- Hvis $i \neq j$, så er $(x_i, y_i) \neq (x_j, y_j)$.
- Den totale summen av $N$ over alle testtilfeller overstiger ikke $10^5$.
Utdata
For hvert testtilfelle, skriv ut svaret på en egen linje.
Eksempler
Eksempelinndata 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
Eksempelutdata 1
15 17 0 20000000000000000
Merk
I det første eksempelet danner punktene $1, 2, 3, 6$ forbundet i denne rekkefølgen en gyldig firkant med areal $15/2$, som er det maksimale blant alle gyldige valg. Firkanten dannet av punktene $1, 2, 4, 5$ har areal $9$, men punktene $1$ og $4$ har samme farge, så den er ugyldig.
I det andre eksempelet finnes det en gyldig firkant, men ingen konveks firkant oppfyller kravene.
I det tredje eksempelet kan ingen gyldig firkant dannes.
Som vist i det fjerde eksempelet kan svaret bli svært stort.