今天，苏菲收到了一款新的版图游戏，游戏的核心要素是在城市之间建立贸易路线。 版图上有 $n$ 个城市，坐标分别为 $(x_1, y_1), (x_2, y_2), \dots, (x_n, y_n)$，任意两个城市不会处于同一坐标。每个城市生产一种类型的货物。贸易路线只能在生产不同种类货物的城市之间建立。在坐标为 $(x_i, y_i)$ 和 $(x_j, y_j)$ 的两个城市之间建立这样一条贸易路线，玩家可以获得 $$(x_i - x_j)^2 + (y_i - y_j)^2$$ 分。

苏菲想知道哪条贸易路线能让她获得最多的分数。请编写一个程序：读取版图的描述，确定能够使获得分数最大化的贸易路线，并将该分数输出到标准输出。

输入格式

输入的第一行包含一个整数 $n$（$2 \le n \le 250\,000$），表示版图上的城市数量。

接下来的 $n$ 行，每行描述一个城市。一个城市的描述由三个整数 $x_i, y_i, t_i$（$-1\,000\,000\,000 \le x_i, y_i \le 1\,000\,000\,000$，$1 \le t_i \le n$）组成，中间用单个空格分隔；其中 $x_i, y_i$ 是第 $i$ 个城市的坐标，而 $t_i$ 是它生产的货物类型。

输入保证总共生产了不止一种类型的货物，且任意两个城市不会处于同一坐标。

输出格式

输出的第一行也是唯一一行，应包含苏菲通过单条贸易路线可以获得的最高分数。

样例

输入样例 1

5
5 4 2
-2 -2 1
10 10 1
8 5 3
5 8 3

输出样例 1

149

说明

使分数最大化的贸易路线连接了坐标为 $(-2, -2)$ 和 $(8, 5)$ 的城市。这条路线可以获得 $149 = 10^2 + 7^2$ 分。还有另一条路线也可以获得相同数量的分数：连接坐标为 $(-2, -2)$ 和 $(5, 8)$ 的城市。