在前往巴黎参加 SWERC 的旅途中，Morgane 为她参观的每一个纪念碑都打了分。在这周的最后一晚，她计划乘坐热气球，并拍摄两张 $180^\circ$ 的城市全景照片，从而获得完美的 $360^\circ$ 视野。她希望两张照片的“美观程度”尽可能接近。

因此，她决定这样做：她选择两个纪念碑，我们称之为“边界纪念碑”，并要求热气球驾驶员在这些纪念碑之间飞行。从那里，她拍摄两张 $180^\circ$ 的照片：每张照片展示巴黎的一侧，两侧均由这两个边界纪念碑界定。每张照片都有一个评分，即该照片所展示的所有纪念碑（包括两张照片共有的边界纪念碑）的评分之和。最后，如果两张照片的评分分别为 $A$ 和 $B$，Morgane 的目标是最小化 $|A - B|$。

热气球的视野使得所有纪念碑都能在两张照片中的任意一张里被看到。

你需要协助 Morgane 选择合适的边界纪念碑。为此，你将获得一份纪念碑列表。对于 Morgane 参观的每一个纪念碑，该列表包含一行数据，指明了纪念碑位置的笛卡尔坐标以及该纪念碑的评分。你需要给出 Morgane 可能拍摄的所有照片对中，两张照片评分之差的最小值。

说明

Morgane 在定位每个纪念碑时非常精确，以至于没有任何三个纪念碑位于同一条直线上。

输入格式

输入包含多行，每行由空格分隔的整数组成： 第一行包含纪念碑的数量 $N$； 接下来的 $N$ 行，每行包含三个整数，分别表示每个纪念碑的 $X$ 坐标、$Y$ 坐标以及该纪念碑的评分 $G$。

数据范围

• $2 \leqslant N \leqslant 4\,000$；
• $0 \leqslant X, Y \leqslant 1\,000\,000\,000$ 且 $1 \leqslant G \leqslant 1\,000\,000\,000$。

输出格式

输出应仅包含一行，即一个整数，表示 Morgane 可能拍摄的照片对中，两张照片评分之差（绝对值）的最小值。

样例

样例输入 1

8
0 0 10
1 1 2
2 1 3
3 2 7
2 3 8
5 2 5
1 5 12
4 5 14

样例输出 1

2