问题描述

程序设计竞赛即将开始，张老师正在绞尽脑汁为学弟学妹们准备训练题，组出一套训练赛。

张老师选出了 $n$ 种类型的题目，为了考察同学们对知识的掌握程度，张老师决定所出的题目中，每一类型的题目至少包含一道。

对于每一种类型的题目，张老师努力找到了 $k$ 道题，其中每一道题对应着一个独立的难度系数。

需要注意的是，在所有类型的题目中，没有任何两道题目拥有相同的难度系数。

现在，张老师想让所出题目的难度跨度尽可能的小，也就是让出的所有题目中最小难度和最大难度尽量接近。

他想请聪明的你帮忙求出最小的难度区间的长度！

输入格式

第一行两个整数 $n, k$（$1 \leq n \leq 10^5$，$1 \leq k \leq 10^5$，保证 $n \times k \leq 10^5$），分别表示题目的种类数和每种题目的数量。

接下来 $n$ 行，每行 $k$ 个整数，第 $i+1$ 行的第 $j$ 个数表示第 $i$ 种题目的第 $j$ 道题的难度系数 $p(i,j)$（$1 \leq p(i,j) \leq 10^9$）。

输出格式

输出一行，表示张老师能选择的最小难度区间的长度。

样例输入

3 3
4 2 1
3 5 7
6 8 9

样例输出

2