25002번 - Board Game 다국어

문제

Today, Sophie received a new board game, whose key element is establishing trade links between cities. There are $n$ cities with coordinates $(x_1,y_1),(x_2,y_2),\ldots,(x_n,y_n)$ on the board, no two of them sharing both coordinates. Each city produces a good of one type. Trade links can be established only between cities producing goods of different kinds. For establishing such a link between a pair of cities with coordinates $(x_i,y_i)$ and $(x_j,y_j),ドル the player receives $$(x_i-x_j)^2+(y_i-y_j)^2$$ points.

Sophie would like to know which trade link would grant her the most points. Write a program that: reads the board description, determines the trade link that maximizes the number of points, and prints this number to the standard output.

입력

In the first line of input, there is an integer $n$ (2ドル \le n \le 250,000円$) that specifies the number of cities on the board. Each of the $n$ lines that follow describes a single city. A city's description consists of a triple of integers $x_i, y_i, t_i$ ($-1,000円 ,000円,000円 \leq x_i,y_i \leq 1,000円,000円,000円,ドル 1ドル\leq t_i \leq n$) separated by single spaces; the numbers $x_i, y_i$ are the $i$-th city's coordinates, whereas $t_i$ is the type of good that it produces.

More than one type of good is produced overall, and no two cities share both coordinates.

출력

The first and only line of output should contain the maximum number of points that Sophie can receive for a single trade link.

제한

노트

The trade link that maximize the number of points links the cities with coordinates $(-2,-2)$ and $(8,5)$. This link yields 149ドル = 10^2 + 7^2$ points. There is also another link that yields the same amount of points: between the cities with coordinates $(-2,-2)$ and $(5,8)$.