eolymp
bolt
Try our new interface for solving problems
Problems

ЗНО

ЗНО

Time limit 1 second
Memory limit 64 MiB

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

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

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

Input data

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

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

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

В усіх тестах NM2∙10^5. У 30% тестів NM10^3.

Output data

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

Examples

Input example #1
3 5
145 171 0 38  100
38  0   0 208 171
0   145 0 100 145
Output example #1
3