Danych jest $N$ różnych punktów na płaszczyźnie 2D, ponumerowanych od $1$ do $N$. Współrzędne punktu $i$ to $(x_i, y_i)$.
Każdy punkt ma pewien kolor. Łącznie jest $N$ kolorów, ponumerowanych od $1$ do $N$, a punkt $i$ ma kolor $c_i$.
Twoim zadaniem jest wybranie czterech punktów o parami różnych kolorach, połączenie ich w dowolnej kolejności i utworzenie czworokąta. Czworokąt ten może mieć kąt wewnętrzny równy dokładnie $180^\circ$, ale żadna para nieprzyległych boków nie może się przecinać.
Rozstrzygnij, czy taki czworokąt można utworzyć. Jeśli tak, niech $S$ oznacza maksymalne możliwe pole spośród wszystkich poprawnych czworokątów i wypisz $2S$ jako liczbę całkowitą. Jeśli nie można go utworzyć, wypisz $0$.
Jest $T$ niezależnych przypadków testowych.
Wejście
Wejście jest podane w następującym formacie:
T case1 case2 : caseT
Tutaj każdy $\text{case}_i$ jest podany w następującej postaci:
N x1 y1 c1 x2 y2 c2 : xN yN cN
- Wszystkie wartości wejściowe są liczbami całkowitymi.
- $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$
- Jeśli $i \neq j$, to $(x_i, y_i) \neq (x_j, y_j)$.
- Suma wartości $N$ po wszystkich przypadkach testowych nie przekracza $10^5$.
Wyjście
Dla każdego przypadku testowego wypisz odpowiedź w osobnym wierszu.
Przykłady
Przykładowe wejście 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
Przykładowe wyjście 1
15 17 0 20000000000000000
Uwaga
W pierwszym przykładzie połączenie punktów $1, 2, 3, 6$ w tej kolejności tworzy poprawny czworokąt o polu $15/2$, co jest wartością maksymalną spośród wszystkich poprawnych wyborów. Czworokąt utworzony przez punkty $1, 2, 4, 5$ ma pole $9$, ale punkty $1$ i $4$ mają ten sam kolor, więc jest niepoprawny.
W drugim przykładzie poprawny czworokąt istnieje, ale żaden czworokąt wypukły nie spełnia wymagań.
W trzecim przykładzie nie da się utworzyć żadnego poprawnego czworokąta.
Jak pokazano w czwartym przykładzie, odpowiedź może być bardzo duża.