Background

Translated from NOI SG 2024 Prelim C.School Photo.

Problem Description

Zane is the principal of the NOI school. The NOI school has $n$ classes, and each class has $s$ students. The height of the $j$-th student in the $i$-th class is $a_{i,j}$.

Now Zane wants to choose one student from each class for a photo, such that among these $n$ students, the difference between the tallest student's height and the shortest student's height is minimized.

Output this minimum value.

Input Format

The first line contains two integers $n, s$.

The next $n$ lines each contain $s$ integers, representing $a$.

Output Format

Output one integer in a single line, representing the answer.

2 3
2 1 8
5 4 7

1

3 3
3 1 4
2 7 18
9 8 10

4

Hint

Sample #2 Explanation

Choose $a_{1,3}, a_{2,2}, a_{3,2}$. The answer is $8-4=4$.

Constraints

For $100\%$ of the testdata, $1 \le n, s \le 1000$, and $1 \le a_{i,j} \le 10^9$.

Translated by ChatGPT 5