The armies of King Bajtomir have just conquered another piece of land that until recently belonged to the kingdom of Bitocja. However, to protect this territory, a stronghold must be built. The king's subjects are very skilled at erecting structures of any size from stone and brick, but the one thing they despise is digging ditches. As is well known, every stronghold must be surrounded by a deep moat for safety.

Fortunately, there are quite a few streams in the conquered territory, so the royal architect, Bajtazar, has decided to use them as a natural moat. He is now wondering where to place the stronghold so that it is surrounded by streams on all sides. Bajtazar is a lover of symmetry, so the stronghold must be built on a square plan. Since it must accommodate a military detachment assigned to defend the conquered territory, it must be as large as possible.

Royal surveyors have mapped the locations of the streams onto a rectangular map. Each stream is a line segment parallel to one of the edges of the map. Segments representing different streams may share more than one common point (i.e., they may flow side-by-side at a negligible distance). The stronghold will be represented on the map by a square. It must be placed such that every point on its perimeter belongs to some segment representing a stream. It does not matter if a segment representing a stream crosses the interior of the square (i.e., the stream flows under the stronghold). Such a stream can be blocked with a grate, and it will be easier for the cook to feed the crocodiles swimming in the moat.

Help Bajtazar and answer the question of whether it is possible to build a stronghold that meets the above requirements. If so, determine the maximum side length of the square representing the stronghold.

Input

The first line of input contains a single integer $n$ ($1 \le n \le 5,000$), representing the number of segments representing streams on the map. The next $n$ lines contain the description of the individual segments - the $i$-th of these lines contains four integers $x_{1}$, $y_{1}$, $x_{2}$, $y_{2}$ ($-10^{9} \le x_{1},\ y_{1},\ x_{2},\ y_{2} \le 10^{9}$, $x_{1} = x_{2}$ or $y_{1} = y_{2}$) indicating that the segment connects points with coordinates $(x_{1}, y_{1})$ and $(x_{2}, y_{2})$.

Output

In the only line of output, print the word NIE if it is impossible to build a stronghold according to the architect's requirements. Otherwise, print a single positive integer representing the maximum side length of the square representing the stronghold.

Examples

Input 1

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

Output 1

2