Fosa

바이토미르 왕의 군대가 얼마 전까지 비토챠 왕국의 영토였던 새로운 땅을 막 정복했다. 이 땅을 지키려면 요새를 세워야 한다. 왕의 백성들은 돌과 벽돌로 아무리 큰 건축물도 능숙하게 쌓지만, 딱 하나 질색하는 일이 있으니 바로 도랑을 파는 것이다. 그리고 잘 알려져 있듯, 모든 요새는 안전을 위해 깊은 해자로 둘러싸여 있어야 한다.

다행히 정복한 땅에는 개울이 꽤 많이 흐르고 있어서, 궁정 건축가 바이타자르는 이 개울들을 천연 해자로 쓰기로 했다. 그는 이제 요새를 어디에 세워야 사방이 개울로 둘러싸일지 고민하고 있다. 바이타자르는 대칭을 사랑하기에 요새는 정사각형 모양이어야 하고, 영토 방어에 배치된 부대를 수용해야 하므로 가능한 한 커야 한다.

왕의 측량사들은 직사각형 지도 위에 개울들의 위치를 표시했다. 각 개울은 지도의 한 변에 평행한 선분이다. 서로 다른 개울을 나타내는 선분들은 한 점보다 많은 공통점을 가질 수도 있다(즉 무시할 만큼 가까이 나란히 흐를 수 있다). 지도에서 요새는 정사각형으로 나타난다. 이 정사각형은 둘레 위의 모든 점이 어떤 개울 선분 위에 놓이도록 배치되어야 한다. 개울 선분이 정사각형의 내부를 가로질러도(즉 개울이 요새 아래로 흘러도) 상관없다. 그런 개울은 격자로 막으면 되고, 요리사가 해자에서 헤엄치는 악어들에게 먹이를 주기도 더 쉬워진다.

바이타자르를 도와, 위 조건을 만족하는 요새를 지을 수 있는지 판단하라. 지을 수 있다면 요새를 나타내는 정사각형의 최대 한 변 길이도 구하라.

첫째 줄에 지도 위 개울을 나타내는 선분의 개수 $n$ ($1 \le n \le 5000$)이 주어진다. 이어지는 $n$개의 줄에 각 선분이 네 정수 $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$ 또는 $y_1 = y_2$)로 주어지며, 이는 선분이 점 $(x_1, y_1)$과 $(x_2, y_2)$를 잇는다는 뜻이다.

건축가의 조건을 만족하는 요새를 지을 수 없다면 NIE를 출력한다. 지을 수 있다면 요새를 나타내는 정사각형의 최대 한 변 길이를 나타내는 양의 정수 하나를 출력한다.

예제를 나타낸 그림.