Problem Description

Xiaoshan and Xiaoxi are playing a matrix game:

There is an $n \times m$ matrix. Xiaoshan can choose a value for each row as the representative value of that row. Xiaoxi will then select two numbers from these representative values and take the absolute difference.

Xiaoshan wants the difference chosen by Xiaoxi to be as small as possible; Xiaoxi wants the difference she selects to be as large as possible.

Please calculate, assuming both players adopt optimal strategies, what is the absolute difference between the two representative values that Xiaoxi ultimately selects?

Input Format

The first line contains two integers $n, m$.

The next $n$ lines each contain $m$ integers.

Output Format

An integer representing the final difference.

3 3
1 2 9
4 5 6
7 8 3

2

Hint

[Sample $1$ Explanation]

When both choose optimal strategies, Xiaoshan selects $\{2,4,3\}$ as the representative values for the three rows. From this set, Xiaoxi chooses the two numbers with the largest difference, $2$ and $4$, resulting in a maximum difference of $|4-2|=2$. This is the minimum maximum difference that Xiaoshan can ensure.

[Constraints]

For $10\%$ of the data, $m=1$.

For another $10\%$ of the data, $n=2$.

For another $20\%$ of the data, $2 \le n \le 8, 2 \le m \le 8$.

For another $30\%$ of the data, $2 \le n \le 100, 2 \le m \le 100$.

For $100\%$ of the data, $2 \le n \le 1000, 1 \le m \le 1000$, and the absolute values of the integers in the matrix do not exceed $10^9$.

Translated by DeepSeek-V3