题目描述

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

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

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

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

输入格式

从文件 $\textit{\textbf{matrix.in}}$ 中读入数据。

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

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

输出格式

输出到文件 $\textit{\textbf{matrix.out}}$ 中。

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

样例

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 \le 8, 2 \le m \le 8$。
• 对于另外 $30\%$ 的数据，保证 $2 \le n \le 100, 2 \le m \le 100$。
• 对于 $100\%$ 的数据，保证 $2 \le n \le 1000, 1 \le m \le 1000$，矩阵中的整数绝对值不超过 $10^9$。