EIT#7067
The examination room for the External Independent Evaluation (EIE) consists of rows, each containing 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 (, ) 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.
The first line of the input contains two natural numbers and — the number of rows and the number of desks per row.
The following lines each contain integers, representing the seating arrangement: the -th number in the (i+1)-th row is zero if the desk at coordinates (, ) is empty; otherwise, it is the school number of the student seated there. School numbers are natural numbers ranging from to 2^{31}-1 inclusive.
The input guarantees that there are at least two students from the same school.
In all test cases, NM \le 2 \cdot 10^5. In of the test cases, NM \le 10^3.
The output should be a single natural number — the quality of the seating arrangement in the class.
Example 1