I - Colors II

Time limit: 3 s
Memory limit: 512 MiB
Languages: C, C++, Java, Python, ... (details)

There are $n$ points on the plane. Each of these points has been assigned a certain color, but not that all points are of the same color. Determine the largest possible (Euclidean) distance between any pair of different-colored points.


Input

The first line of the input contains a single integer $n$ $(2 \le n \le 250 000)$. Each of the following $n$ lines describes a single point. A point's description consists of three integers $x_i$, $y_i$ and $c_i$ $(-10^9 \le x_i, y_i \le 10^9, 1 \le c_i \le n)$ separated by single spaces; the numbers $x_i$ and $y_i$ are the $i$-th point's coordinates, and $c_i$ is the id of the point's color.

There are at least two different colors and no two points have the same coordinates.

Output

The first and only line of the output should contain the square of the maximum distance between two points of different colors.

Sample test(s)

Input
3 0 0 1 1 1 2 2 2 1
Output
2
Input
4 0 0 1 0 1 2 1 0 3 1 1 4
Output
2