Однажды Эркюль Пуаро заскучал, и Мсье Бук решил его развлечь.
Мсье Бук взял клетчатый листок бумаги и отметил на нём несколько точек с целочисленными координатами. После этого он попросил Эркюля узнать максимальное d такое, что отмеченные точки можно разбить на два непустых множества так, чтобы для каждой пары точек из разных множеств расстояние было больше или равно d.
Так как мсье Бук большой любитель целых чисел, в качестве ответа он попросил Эркюля выдать d2. Можно доказать, что d2 — всегда целое число при данных ограничениях.
Эркюль быстро справился с данной задачей, а справитесь ли Вы?
Первая строка содержит одно число n — количество точек, которые отметил мсье Бук (2 ≤ n ≤ 2000). Каждая из последующих n строк содержит по два целых числа x, y — координаты точек ( - 109 ≤ x, y ≤ 109). Все отмеченные точки различны.
Выведите одно число равное d2.
4
0 1
1 0
0 0
1 1
1
7
0 1
1 0
0 0
1 1
1 3
2 2
2 3
2