На двумерной плоскости даны $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$ одного цвета, поэтому он некорректен.
Во втором примере корректный четырёхугольник существует, однако ни один выпуклый четырёхугольник не удовлетворяет требованиям.
В третьем примере невозможно образовать ни одного корректного четырёхугольника.
Как показано в четвёртом примере, ответ может быть очень большим.