The difference between this problem and "Colors II" is in bold.

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. All these points lie on a straight line.

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.

It is guaranteed that all $n$ points lie on a straight line.

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

Input

3
0 0 1
1 1 2
2 2 1

Output

2