题目描述

给定 $n$ 条三维空间中的线段。第 $i$ 条线段在输入时一端位于 $(0,0,0)$，另一端位于 $(x_i,y_i,z_i)$。

你可以任意平移这些线段，但不能旋转或镜像它们。需要把所有线段首尾相接，组成一条单一的、不自交的开放折线。除相邻线段在公共端点处相接外，任意两条线段都不能相交或接触。

设最终折线的两个端点之间的欧氏距离为 $D$。请最大化 $D$，并输出 $D^2$。

输入中即使有多条空间位置完全重合的线段，也应把它们视为不同线段。

输入格式

第一行输入整数 $n$。

接下来 $n$ 行，每行三个整数 $x_i,y_i,z_i$，描述第 $i$ 条线段的方向向量。

输出格式

输出一个整数，表示折线两个端点之间距离平方的最大值。

数据范围

• $1\le n\le50$；
• $-10000\le x_i,y_i,z_i\le10000$；
• 每条线段长度均非零。

样例

输入

7
1000 0 0
1000 1 0
1000 -1 0
1 1000 0
0 1000 0
-1 1000 0
10 -1 0

输出

18066101