Minimize Height Difference

Zane is the headmaster of NOI School which has \(n\) classes and each class has \(s\) students. The height of the \(j\)th student in the \(i\)th class is given by \(a_{i,j}\). Your task is to choose one student from each class such that the difference between the tallest and the shortest of the chosen students is minimized. Output this minimum difference.

Note: All formulas are in \(\LaTeX\) format.

inputFormat

The first line contains two integers \(n\) and \(s\) \((1 \leq n, s \leq 10^5)\), representing the number of classes and the number of students per class respectively. This is followed by \(n\) lines, each containing \(s\) integers. The \(j\)th integer in the \(i\)th line is \(a_{i,j}\), representing the height of the student.

outputFormat

Output a single integer: the minimum possible difference between the maximum and minimum heights among the chosen students.

sample

3 3
1 5 9
3 6 10
2 4 8

2