ЗНО

Аудиторія для проведення ЗНО (зовнішнього незалежного оцінювання) містить N рядів по M парт в кожному. За кожною партою сидить не більше ніж один учень, а місця визначаються жеребкуванням. Незважаючи на це, може трапитись, що учні з однієї школи сидять поруч одне з одним. Відповідальний за проведення ЗНО в одному класі нудьгує і вирішує визначити "якість" розташування учнів за партами.

Запровадимо прямокутні координати парт таким чином: (ряд, місце). Назвемо відстанню між учнями за партами з координатами (x, y) та (x', y') величину d = |x – x'| + |y – y'|. Назвемо якістю розсадки в класі найменшу відстань між двома учнями з однієї школи.

Визначте якість розсадки учнів в класі, якщо задано координати розта­шу­вання і номери шкіл всіх учнів.

Вхідні дані

Перший рядок вхідних даних містить два натуральних числа N, M — кількість рядів в класі й кількість парт в одному ряді.

Наступні N рядків містять по M цілих чисел, що задають розташування учнів: j-те число (i+1)-го рядка дорівнює нулеві, якщо парта з координатами (i, j) порожня, інакше — номеру школи учня, який сидить за цією партою. Номери шкіл — натуральні числа від 1 до 2^31–1 включно.

Вхідний файл містить принаймні два однакових номери шкіл.

В усіх тестах NM ≤ 2∙10^5. У 30% тестів NM ≤ 10^3.

Вихідні дані

Єдиний рядок вихідного файлу має містити одне натуральне число — якість розсадки в класі.

Приклади