ЗНО#7067

ЗНО

1 секунда

64 мегабайти

Легка

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

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

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

Вхідні дані

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

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

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

В усіх тестах $N M \leq 2 \cdot 1 0^{5}$ NM \le 2 \cdot 10^5. У $30%$ тестів $N M \leq 1 0^{3}$ NM \le 10^3.

Вихідні дані

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

Приклади

Приклад 1