На двовимірній площині дано $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$ мають однаковий колір, тому він є некоректним.
У другому прикладі коректний чотирикутник існує, проте жоден опуклий чотирикутник не задовольняє вимоги.
У третьому прикладі неможливо утворити жодного коректного чотирикутника.
Як показано в четвертому прикладі, відповідь може бути дуже великою.