Given $n$ sequences, each containing $m$ elements, choose exactly one element from each sequence such that the difference between the largest and smallest chosen elements is minimized.

Input

• The first line contains two integers $n$ and $m$.
• The next $n$ lines each contain $m$ integers, representing a sequence.

Output

• Print a single integer, the minimum possible difference between the largest and smallest chosen elements.

Constraints

• $1 \leq n, m \leq 1000$.
• The absolute value of the numbers in the sequences does not exceed $10^9$.

Example

Input:

3 4
12 16 67 43
7 17 68 48
14 15 77 54

Output:

2