题目描述

小山和小西在玩一个矩阵游戏：

有一个 $n\times m$ 的矩阵，小山可以为每一行选择一个值作为该行的代表值。小西会从这些代表值中选择两个数作差（取绝对值）。

小山希望小西选出的差值尽可能小；小西希望自己选出的差值尽可能大。

请你计算，在两个人都采取最优策略的情况下，小西最终选出的两个代表值的差的绝对值是多少？

输入格式

第一行两个整数 $n,m$。

接下来 $n$ 行，每行 $m$ 个整数。

输出格式

一个整数，表示最终的差值。

3 3
1 2 9
4 5 6
7 8 3

2

提示

【样例 $1$ 解释】

两人都选择最优策略时，小山选择 $\{2,4,3\}$ 作为三行的代表值。在此集合下，小西会选择差值最大的两个数 $2$ 和 $4$，得到的最大差值为 $|4-2|=2$。这是小山能够确保的最小最大差值。

【数据范围】

对于 $10\%$ 的数据，保证 $m=1$。

对于另外 $10\%$ 的数据，保证 $n=2$。

对于另外 $20\%$ 的数据，保证 $2\le n\le8,2\le m\le8$。

对于另外 $30\%$ 的数据，保证 $2\le n\le100,2\le m\le100$。

对于 $100\%$ 的数据，保证 $2\le n\le1000,1\le m\le1000$，矩阵中的整数绝对值不超过 $10^9$。