Problem description

Firma telekomunikacyjna JANUSZKOM postanowiła rozstawić N przekaźników radiowych wzdłuż kraju. Przekaźniki ustawione będą na jednej prostej. Dla każdego z przekaźników wyznaczone zostały dwie możliwe współrzędne, na którym powinien znaleźć się dany przekaźnik. Dla każdego z przekaźników należy wybrać jedną z tych współrzędnych. Ponadto chcielibyśmy, żeby przekaźniki zostały rozstawione możliwie równomiernie. Formalnie, chcielibyśmy, żeby minimalna odległość między pewną parą przekaźników była największa możliwa.

Oczywiście to zadanie zostało powierzone Tobie. Napisz program, który wyznaczy wartość największej możliwej minimalnej odległości między pewną parą przekaźników.

Wejście

W pierwszym wierszu wejścia dana jest jedna liczba naturalna N oznaczająca liczbę przekaźników. W następnych N wierszach dany jest opis możliwych współrzędnych każdego z przekaźników. i-ty opis składa się z dwóch liczb x_i, y_i oddzielonych pojedynczą spacją i oznaczające możliwe położenie i-tego przekaźnika.

Wyjście

W pierwszym i jedynym wierszu wyjścia powinna znaleźć się jedna liczba całkowita oznaczającą maksymalną minimalną odległość między pewną parą przekaźników.

Ograniczenia

2 ≤ N ≤ 10 000, 1 ≤ x_i, y_i ≤ 10⁹.

W testach wartych 10% punktacji zachodzi dodatkowy warunek N ≤ 20.

W testach wartych 50% punktacji zachodzi dodatkowy warunek N ≤ 2 000.

Przykład

3
1 3
2 5
1 9

4