2차원 평면 위에 서로 다른 $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$의 색상이 같으므로 올바르지 않습니다.
두 번째 예제에서는 올바른 사각형이 존재하지만, 조건을 만족하는 볼록사각형은 없습니다.
세 번째 예제에서는 올바른 사각형을 만들 수 없습니다.
네 번째 예제에서 볼 수 있듯이 답은 매우 클 수 있습니다.