题目背景

翻译自 NOI SG 2024 Prelim C.School Photo。

题目描述

Zane 是 NOI 学校的校长。NOI 学校有 $n$ 个班，每个班有 $s$ 名同学。第 $i$ 个班中的第 $j$ 名同学的身高是 $a_{i,j}$。

现在 Zane 想从每个班上选出一名同学拍照，使得这 $n$ 名同学中最高的同学和最低的同学的身高差最小。

请你输出这个最小值。

输入格式

第一行，两个整数 $n,s$；

接下来 $n$ 行，每行 $s$ 个整数，表示 $a$。

输出格式

一行一个整数表示答案。

2 3
2 1 8
5 4 7

1

3 3
3 1 4
2 7 18
9 8 10

4

提示

【样例 #2 解释】

选择 $a_{1,3},a_{2,2},a_{3,2}$，答案为 $8-4=4$。

【数据范围】

对于 $100\%$ 的数据，$1\le n,s \le 1000,1\le a_{i,j} \le 10^9$。