EIT
The examination room for the External Independent Evaluation (EIE) consists of N rows, each containing M desks. Each desk can seat at most one student, and seating is assigned randomly. However, it's possible for students from the same school to end up sitting next to each other. The person overseeing the EIE in this room, feeling a bit bored, decides to evaluate the "quality" of the seating arrangement.
Let's define a coordinate system for the desks: (row, seat). The distance between students sitting at desks with coordinates (x, y) and (x', y') is given by d = |x - x'| + |y - y'|. The quality of the seating arrangement is defined as the minimum distance between any two students from the same school.
Your task is to determine the quality of the seating arrangement, given the seating coordinates and the school numbers of all students.
Input
The first line of the input contains two natural numbers N and M — the number of rows and the number of desks per row.
The following N lines each contain M integers, representing the seating arrangement: the j-th number in the (i+1)-th row is zero if the desk at coordinates (i, j) is empty; otherwise, it is the school number of the student seated there. School numbers are natural numbers ranging from 1 to 2^31-1 inclusive.
The input guarantees that there are at least two students from the same school.
In all test cases, NM ≤ 2∙10^5. In 30% of the test cases, NM ≤ 10^3.
Output
The output should be a single natural number — the quality of the seating arrangement in the class.