ЕГЭ
Аудитория для проведения ЕГЭ (единого государственного экзамена) состоит из 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.
Выходные данные
Единственная строка выходного файла должна содержать одно натуральное число — качество рассадки в классе.