巴伊托米尔国王的军队刚刚征服了一块新领土，这片领土直到最近还属于比托齐亚王国。然而，为了能够保护这片土地，必须建造一座堡垒。国王的臣民非常擅长用石头和砖头建造任何规模的建筑，但有一件事他们非常不喜欢，那就是挖壕沟。众所周知，为了安全，任何堡垒都必须被深壕环绕。

幸运的是，在新征服的领地上有不少溪流，所以御用建筑师巴伊塔扎尔决定利用这些溪流作为天然的壕沟。他现在正在思考，应该把堡垒建在什么地方，才能让堡垒四面都被溪流包围。巴伊塔扎尔非常喜欢对称，因此堡垒必须以正方形为平面图形。由于这座堡垒要容纳被派驻守新领地的军队，所以必须尽可能大。

王室的测量员已经在一张矩形地图上标出了所有溪流的位置。每条溪流在地图上表现为一条与地图边平行的线段。代表不同溪流的线段可能会有多个公共点（也就是说，它们可以以可以忽略的距离并排流动）。堡垒在地图上将用一个正方形表示。这个正方形必须被放置在地图上，使得其每一个边界上的点都属于某条代表溪流的线段。我们不在意如果某条溪流线段穿过了正方形的内部（也就是说，溪流从堡垒下方流过）。这种情况下，可以用栅栏封住溪流，而厨师也更容易给壕沟里的鳄鱼喂食。

请帮助巴伊塔扎尔，回答是否能建造满足上述要求的堡垒。如果可以，请计算代表堡垒的正方形的最大边长。

输入格式

输入的第一行包含一个整数 $n$ ($1 \leq n \leq 5,000$)，表示地图上代表溪流的线段数量。接下来的 $n$ 行描述各条线段——第 $i$ 行包含四个整数 $x_{1}$、$y_{1}$、$x_{2}$、$y_{2}$ ($-10^{9} \leq x_{1}, y_{1}, x_{2}, y_{2} \leq 10^{9}$，$x_{1} = x_{2}$ 或 $y_{1} = y_{2}$)，表示这条线段连接坐标为 ($x_{1}, y_{1}$) 和 ($x_{2}, y_{2}$) 的两个点。

输出格式

输出仅一行。如果无法按照建筑师的要求建造堡垒，输出单词 NIE。否则，输出一个正整数，表示代表堡垒的正方形的最大边长。

样例

输入

6
-1 0 2 0
0 2 3 2
0 -1 0 2
2 0 2 3
1 1 1 3
2 3 1 3

输出

2