Задача D. Прыжки ≡

Условие

Одна из дворовых игр детства автора задачи называлась "Прыжки". Рисовался мелом прямоугольник, разбивался на квадраты с числами внутри от 1 до k (по числу квадратов) и потом детвора пыталась по очереди пропрыгать по всем квадратам в порядке возрастания их номеров таким образом, чтобы ни разу не приземлиться на линии сетки.

Назовем расстоянием прыжка между квадратами с числами x и x + 1 расстояние между центрами этих квадратов (считая сторону квадрата равной 1). Так, расстояние прыжка между квадратами с числами 1 и 2 на приведенном на рисунке поле равно √2, между квадратами с числами 2 и 3 равно 1, между квадратами с числами 3 и 4 равно √10 (вычисляется по теореме Пифагора).

Тимофей еще маленький и прыгает не очень далеко, а квадраты с числами могут располагаться друг от друга на значительном расстоянии. По данному полю определите максимальное расстояние прыжка, требуемое для того, чтобы пройти испытание.

Формат входных данных

Первая строка входного файла содержит два натуральных числа, записанных через пробел: n и m. В следующих n строках через пробел расположено по m натуральных чисел x_i — номера квадратов игрового поля. Гарантируется, что все x_i составляют некоторую перестановку чисел от 1 до n × m.

Формат выходных данных

Выведите одно натуральное число — квадрат максимального расстояния прыжка в данном поле.

Ограничения

1 ≤ n, m ≤ 10⁵

2 ≤ n × m ≤ 10⁵

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

Пояснение к примеру

Наибольшее расстояние прыжка для данного в примере поля требуется для того, чтобы добраться с квадрата номер 3 до квадрата номер 4 (оно равно √10. Требуется вывести натуральное число — квадрат этого расстояния.

Примеры тестов

4 3
8 4 11
5 7 12
1 10 9
6 2 3

10